一血代码：
A
Description
分析有几种方法使得输出为三个数的最大数
Solution
语义分析（不用复制下来运行的拉~）
Code
Code by Emanon1
2
3
4
5
6
7
8
9
10
11
12
13
using namespace std;
int main()
{
printf("5\n");
printf("1 3 4 8 10");
return 0;
}
B
Description
给出序列$X$和序列$Y$，求$X_i$异或$Y_j$后有少个数字在这$2n$个数里的有序对数量的奇偶性。
Solution
异或性质: $a\oplus b = c$，那么$c \oplus a = b$ 决定总是两对两对出现。
Code
Code by Emanon1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn], b[maxn];
int main()
{
int n;
cin >> n;
for(int i = 0;i < n; i++) cin >> a[i];
for(int i = 0;i < n; i++) cin >> b[i];
cout << "Zhuangzhuang Mei Mei Mei" << endl;
return 0;
}
C
Description
给图的初始权值和期望权值，进行操作后能后实现。
Solution
对每个联通块判断是否权值和一样。
Code
Code by UnitsPR1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
int father[200000 + 1];
long long a[200000 + 1];
long long b[200000 + 1];
int find(int x)
{
if (x == father[x]) return father[x];
father[x] = find(father[x]);
return father[x];
}
inline void merge(int u,int v)
{
u = find(u);v = find(v);
if (u != v)
{
father[u] = v;
a[v] += a[u];
b[v] += b[u];
}
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
for(int i = 1;i <= n;i++) father[i] = i;
for(int i = 1;i <= n;i++) scanf("%lld",&a[i]);
for(int i = 1;i <= n;i++) scanf("%lld",&b[i]);
for(int i = 1;i <= m;i++)
{
int u,v;
scanf("%d %d",&u,&v);
merge(u,v);
}
bool bl = 1;
for(int i = 1;i <= n;i++)
{
int x = find(i);
if (a[x] != b[x])
{
bl = 0;
printf("azhe\n");
break;
}
}
if (bl) printf("yingyingying\n");
}
D
Description
给定一个长度为 n 字符串，交换相邻的字符，问能不能形成回文串，如果能输出最少操作次数。
Solution
把字符移动到最外边最优，从左往右 用 Fenwick Tree 维护。
Code
Code by Devour_1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
const int INF = 0x3f3f3f3f;//1.06e9大小
const double PI = acos ( -1 );
const double eps = 1e-6;
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
template<typename t>void read(t &x)
{
char ch=getchar();x=0;int f=1;
while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x=x*f;
}
const int maxn = 2e5+20;
const int mod = 1e9+7;
int bit[maxn] ,a[maxn];
int n ;
void add(int i,int x)
{//迭代单点修改
while(i<=n)
{
bit[i]+=x;
i+=lowbit(i);
}
}
int sum(int i)
{
int s=0;
while(i>0)
{
s+=bit[i];
i-=lowbit(i);
}
return s;
}
string s ;
vector<int >loc[26];
int main()
{
cin>>s;n = s.size();
int cnt =0;
for(int i =0;i<n;++i)loc[s[i]-'a'].push_back(i);
for(int i =0;i<26;++i)cnt+=(loc[i].size()&1);
if(cnt>1)printf("rkmdsxmds buKeai\n");
else
{
//printf("^_^\n");
ll ans =0;
int tot =0;
for(int i =0;i<n&&tot<n/2;++i)
{
if(a[i])continue;
else
{
int re = s[i] -'a';
int co = loc[re].size()-1;
if(loc[re][co]==i)
{//奇数个当然可以遇到自己啦，于是这个时候就要处理答案
ans+=(n/2 - tot);
continue;
}
ans+=(n -1 -loc[re][co])-( sum(n-1)-sum(loc[re][co]) );
//printf("%d %lld %d %d\n",i,ans,sum(n-1),sum(co+1));
a[ loc[re][co] ] = 1;
add(loc[re][co],1 );
loc[re].pop_back();
tot++;
}
}
printf("%lld\n",ans);
}
return 0;
}
E
Description
对于长度为$n$的字符串，计算含本质不同的回文子串数量最少的字符串个数
Solution
Code
Code by Yukari171
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
using namespace std;
int main()
{
int T;
long long n;
scanf("%d",&T);
while(T--)
{
scanf("%lld",&n);
if(n==1)puts("62");
if(n==2)puts("3844");
if(n==3)puts("238328");
if(n>3)puts("226920");
}
}
/*
62*61*60=226920
62^3
aba
*/
F
Description
Solution
求一条欧拉路
Code
Nobody
G
Description
模拟
Solution
模拟题意。写完就行。
Code
Code by PaperCube1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
using namespace std;
bool leap(int yr) { return yr % 400 == 0 || (yr % 4 == 0 && yr % 100 != 0); }
const int days_of_month[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int get_day(int yr, int mo) {
if (mo != 2)
return days_of_month[mo];
return leap(yr) ? 29 : 28;
}
int compose(int y, int m, int d) { return y * 10000 + m * 100 + d; }
void inc(int &y, int &m, int &d) {
d++;
if (d > get_day(y, m)) {
d = 1;
m++;
}
if (m > 12) {
m = 1, y++;
}
}
void read_date(int &y, int &m, int &d) { scanf("%d-%d-%d", &y, &m, &d); }
int read_int() {
int v;
scanf("%d", &v);
return v;
}
void make_wd(int &v) {
int x = v - 1;
x %= 7;
v = x + 1;
}
bool workday(int m, int d) {
static int n1 = compose(0, 2, 11), n2 = compose(0, 7, 11),
n3 = compose(0, 8, 23), n4 = compose(0, 1, 29);
int v = compose(0, m, d);
return (v >= n1 && v <= n2) || v >= n3 || v <= n4;
}
int r[8];
int main() {
int y, m, d, w;
int y2, m2, d2;
read_date(y, m, d);
read_date(y2, m2, d2);
w = read_int();
for (; compose(y, m, d) <= compose(y2, m2, d2); inc(y, m, d), w++) {
make_wd(w);
if (!workday(m, d))
continue;
if (d == 1)
r[3]++;
else if (d == get_day(y, m))
r[4]++;
else if ((m == 2 && d == 14) || (m == 8 && d == 25)) {
r[1]++;
} else {
r[w]++;
}
}
for (int i = 1; i <= 7; i++){
cout << r[i] << endl;
}
}
H
Description
每次能走$[1,k]$个格子，问从$1$走到$n$有几种方法
Solution
当$k = 2$时，就是每次能走$1,2$格，就是斐波那契数列,$f[i] = f[i - 1] + f[i - 2]$
对于 $k$，$f[i] = \sum_{j = 1}^k f[i - j]$， 矩阵维护一下。
Code
Code by1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
mt19937 rnd(time(nullptr));
typedef unsigned long long LL;
template <class T>
using min_queue = priority_queue<T, vector<T>, greater<T> >;
template <class T>
using max_queue = priority_queue<T>;
template <class A, class B>
ostream& operator<<(ostream& s, pair<A, B> const& a) {
return s << "(" << get<0>(a) << ", " << get<1>(a) << ")";
}
template <size_t n, typename... T>
typename std::enable_if<(n >= sizeof...(T))>::type print_tuple(
std::ostream&, const std::tuple<T...>&) {}
template <size_t n, typename... T>
typename std::enable_if<(n < sizeof...(T))>::type print_tuple(
std::ostream& os, const std::tuple<T...>& tup) {
if (n != 0) os << ", ";
os << std::get<n>(tup);
print_tuple<n + 1>(os, tup);
}
template <typename... T>
std::ostream& operator<<(std::ostream& os, const std::tuple<T...>& tup) {
os << "(";
print_tuple<0>(os, tup);
return os << ")";
}
template <class T>
ostream& print_collection(ostream& s, T const& a) {
s << '[';
for (auto it = begin(a); it != end(a); ++it) {
s << *it;
if (it != prev(end(a))) s << ", ";
}
return s << ']';
}
template <class T, class U>
ostream& operator<<(ostream& s, map<T, U> const& a) {
return print_collection(s, a);
}
template <class T>
ostream& operator<<(ostream& s, set<T> const& a) {
return print_collection(s, a);
}
template <class T>
ostream& operator<<(ostream& s, vector<T> const& a) {
return print_collection(s, a);
}
double __startG = clock();
void resetG() { __startG = clock(); }
double curTime() { return (clock() - __startG) / CLOCKS_PER_SEC; }
bool stopNow(double ttl) { return ttl < curTime(); }
template <typename T = int>
T get_signed_int() {
char c = getchar();
T ret = 0, neg = 0;
while (c != '-' && !isdigit(c)) c = getchar();
if (c == '-') neg = 1, c = getchar();
do {
ret = (ret << 3) + (ret << 1) + c - '0';
} while (isdigit(c = getchar()));
return neg ? -ret : ret;
}
template <typename T>
void print_int(T x) {
static char s[60], *s1;
s1 = s;
if (!x) *s1++ = '0';
if (x < 0) putchar('-'), x = -x;
while (x) *s1++ = (x % 10 + '0'), x /= 10;
while (s1-- != s) putchar(*s1);
}
const LL INF = 0x3f3f3f3f3f3f3f3fll;
const double PI = acos(-1.0), eps = 1e-7;
const int inf = 0x3f3f3f3f, ninf = 0xc0c0c0c0, mod = 1000000007;
const int max3 = 1100, max4 = 11100, max5 = 200100, max6 = 2000100;
int dp[100];
// k = 1, 1.......1
// k = 2, 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946
// k = 3, 1 2 4 7 13 24 44 81 149 274 504 927
// k = 4, 1 2 4 8 15 29 56 108 208 401 773
// k = 5, 1 2 4 8 16 31 61 120 236 464 912 1793 3525 6930 13624 26784
// k = 6, 1 2 4 8 16 32 63 125 248 492 976 1936 3840 7617 15109 29970 59448
// k = 7, 1 2 4 8 16 32 64 127 253 504 1004 2000 3984 7936 15808 31489 62725 124946
// k = 8, 1 2 4 8 16 32 64 128 255 509 1016 2028 4048 8080 16128 32192 64256 128257 256005
// k = 9, 1 2 4 8 16 32 64 128 256 511 1021 2040 4076 8144 16272 32512 64960 129792 259328
// k = 10,1 2 4 8 16 32 64 128 256 512 1023 2045 4088 8172 16336 32656 65280 130496 260864
/*
k = 2
[1, 1]
[1, 0]
k = 3
[1, 1, 1;
0, 0, 1;
1, 0, 0]
k = 6
[0, 1, 0, 0, 0, 0;
0, 0, 1, 0, 0, 0;
0, 0, 0, 1, 0, 0;
0, 0, 0, 0, 1, 0;
0, 0, 0, 0, 0, 1;
1, 1, 1, 1, 1, 1]
k = 10
{0,1,0,0,0,0,0,0,0,0},
{0,0,1,0,0,0,0,0,0,0},
{0,0,0,1,0,0,0,0,0,0},
{0,0,0,0,1,0,0,0,0,0},
{0,0,0,0,0,1,0,0,0,0},
{0,0,0,0,0,0,1,0,0,0},
{0,0,0,0,0,0,0,1,0,0},
{0,0,0,0,0, 0,0,0,1,0},
{0,0,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}}.
*/
int n;
struct Matrix {
LL val[124][124];
void Zero() {memset(val,0,sizeof(val));}
void Init(){
Zero();
for(int i=0;i<124;i++)
val[i][i]=1;
}
Matrix operator *( const Matrix &b );
} A;
Matrix Matrix::operator *( const Matrix &b ) {
Matrix temp;
temp.Zero();
for( int i = 0 ; i < n ; i ++ ){
for( int k = 0 ; k < n ; k ++ ){
if( val[i][k] ){
for( int j = 0 ; j < n; j ++ ){
temp.val[i][j]+=val[i][k]*b.val[k][j];
temp.val[i][j] %= mod;
}
}
}
}
return temp;
}
Matrix quickpow(Matrix A,int m) {
Matrix temp;
temp.Init();
while( m ) {
if( m&1 ) temp = temp*A;
A = A*A;
m >>= 1;
}
return temp;
}
int main() {
int T, N, K;
cin >> T;
while (T--) {
cin >> N >> K;
n = K;
A.Zero();
for (int i = 0; i < n - 1; i++) {
A.val[i][i + 1] = 1;
}
for (int i = 0; i < n; i++) {
A.val[n - 1][i] = 1;
}
A = quickpow(A, N);
printf("%llu\n", A.val[n - 1][0]);
}
return 0;
}
I
Description
找到一个子集，使得子集序号的异或和不为0且开心值和最大。
Solution
先按开心值进行排序，对每一样泥巴尝试插入线性基即可（线性基一个性质是线性基内任意一些数异或起来不为 $0$。
Code
Code by axp1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
using namespace std;
const int N=1e5+10;
typedef long long ll;
typedef pair<ll,ll> ii;
set<ll> se;
bool check(ll x){
for(auto i=se.rbegin();i!=se.rend();++i){
if((x^(*i))<x)
x^=*i;
//cout<<i<<' ';
}
//cout<<endl<<x<<": "<<tx<<endl;
if(x==0)return 0;
se.insert(x);
return 1;
}
ii a[N];
int n;
int main(){
cin>>n;
for(int i=0;i<n;++i)cin>>a[i].first>>a[i].second;
sort(a,a+n,[](const ii& a, const ii&b){return a.second>b.second;});
ll ans=0;
for (int i=0;i<n;++i){
if(check(a[i].first))
ans+=a[i].second;
}
cout<<ans<<endl;
return 0;
}
J
Description
每个字符串压缩，每个字符串不同，使字符串总和最小。
Solution
对于字符串，建字典树，每个结点维护字符串长度多重集合，从下往上做启发式合并，若当前结点没有被标记，则从多重集合中选最大数值替换为当前节点字符串长度，$dsu on tree$，$O(nlog^2n)$
Code
Nobody
K
Description
Solution
ans=$233+max(max(\sum_{i = 1}^na_i), 0)$
Code
Code by yzbsy1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
using namespace std;
int main(){
int n;
scanf("%d",&n);
long long st=233,maxx=233,x;
for(int i=0;i<n;i++){
scanf("%lld",&x);
st+=x;
maxx=max(maxx,st);
}
printf("%lld",maxx);
return 0;
}
L
Description
Solution
对每一行建 $Splay$，离线把每个 $4$ 操作连成一棵树，$dfs$ 即可
Code
Nobody
M
Description
$f[i]=f[i-1]+2*f[i-2]\%100000$。
Solution
数组模拟过程，多组输入要学会。
Code
Code by Bi081
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e6+10;
const int mod = 100000 ;
ll a[N],n,x;
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
while(cin>>n>>x){
a[1] = x%mod;
for(int i=2; i<=n; i++) a[i] = a[i-1] % mod+ a[i-2]*2%mod;
cout<<a[n]%mod<<endl;
}
return 0;
}