赛时rank3，95，30，40，5，5
赛后hack，rank7，40，30，40，5，5
\(太CAI了\)
T1 分糖果
简要题意：
将\(n\)个数分成最多组，使得每组有\(3\)个人，每组的数字和能被\(3\)整除，输出组数和方案
\(n≤10^5,1≤a_i≤10^5\)
\(solution:\)
将每个数\(\mod3\)存入，则有三类:余数为0，1，2；
可以的方案有三种\(0,0,0\)，\(0,1,2\)，\(1,1,1\)，\(2,2,2\)
考虑到\(0,1,2\)不少于三个时无意义，所以枚举\(0,1,2\)的个数,时间复杂度\(O(n)\)
\(code:\)
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
const int N = 1e5 + 10;
int n,a[N];
queue<int> tot[3];
signed main(){
#ifndef ONLINE_JUDGE
infile("in.in");outfile("out.out");
#else
#endif
cin.tie(0)->sync_with_stdio(false);
cout.tie(0)->sync_with_stdio(false);
cin>>n;
for(int i = 1;i <= n; ++i) cin>>a[i];
for(int i = 1;i <= n; ++i) tot[a[i]%3].push(i);
int emm = min({tot[0].size(),tot[1].size(),tot[2].size()});
ll ans = 0,res = 0;
for(int i = 0;i <= min(emm,2); ++i){
if(ans < (tot[0].size()-i)/3+(tot[1].size()-i)/3+(tot[2].size()-i)/3+i){
ans = (tot[0].size()-i)/3+(tot[1].size()-i)/3+(tot[2].size()-i)/3+i;
res = i;
}
}
cout<<ans<<'\n';
if(!ans) return 0;
while(res--){
cout<<tot[0].front()<<' '<<tot[1].front()<<' '<<tot[2].front()<<'\n';
tot[0].pop();tot[1].pop();tot[2].pop();
}
while(tot[0].size()>=3){
cout<<tot[0].front()<<' ';tot[0].pop();
cout<<tot[0].front()<<' ';tot[0].pop();
cout<<tot[0].front()<<'\n';tot[0].pop();
}
while(tot[1].size()>=3){
cout<<tot[1].front()<<' ';tot[1].pop();
cout<<tot[1].front()<<' ';tot[1].pop();
cout<<tot[1].front()<<'\n';tot[1].pop();
}
while(tot[2].size()>=3){
cout<<tot[2].front()<<' ';tot[2].pop();
cout<<tot[2].front()<<' ';tot[2].pop();
cout<<tot[2].front()<<'\n';tot[2].pop();
}
}
T2 乒乓球
找循环节，不会打，待填
T3 与或
简要题意：
给定一个长度为\(n\)的数组\(a\,\)\((n\le 10^5)\),和\(k\)个|运算符，\(n-k-1\)个&运算符，用以上\(n-1\)个符号将数组连接起来，从左到右计算结果，使得结果最大并且符号序列的字典序最小，输出结果和符号序列。
样例输入1
4 2
1 3 5 7
样例输出1
7
||&
样例输入2
4 1
1 3 5 7
样例输出2
7
&&|
\(solution:\)
有一个结论：&放在|前一定不劣。
证明：假设有三个相邻的位置x,y,z，左边是∣，右边是&，那么结果最大是z，假设左边是&，右边是∣，那么结果最小是z。
考虑按位贪心，对于当前位置，若放了|后后续最大答案仍是理论最大值，则放|，反之，则放&。
\(code:\)
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
const int N = 2e5 + 10;
int n,k,sum[N][61];
ll a[N];
inline ll check(int pos,ll val,int k){
if(pos <= n - k){
vector<int> t(60);
for(int i = 0;i < 60; ++i)
t[i] = sum[n-k][i] - sum[pos-1][i];
for(int i = 0;i < 60; ++i)
if(t[i] != (n-k-pos+1) && ((val>>i)&1))
val ^= (1ll<<i);
}
if(k >= 1){
vector<int> t(60);
for(int i = 0;i < 60; ++i) t[i] = sum[n][i] - sum[n - k][i];
for(int i = 0;i < 60; ++i) if(t[i]) val |= (1ll<<i);
}
return val;
}
signed main(){
#ifdef ONLINE_JUDGE
infile("in.in");outfile("out.out");
#else
#endif
cin.tie(0)->sync_with_stdio(false);
cout.tie(0)->sync_with_stdio(false);
cin>>n>>k;
for(int i = 1;i <= n; ++i) cin >> a[i];
for(int i = 1;i <= n; ++i){
for(int j = 0;j < 60; ++j) sum[i][j] = sum[i-1][j];
for(int j = 0;j < 60; ++j) sum[i][j] += ((a[i]>>j)&1);
}
ll mx = check(2,a[1],k);
cout<<mx<<'\n';
int nowk = k;ll ans = 1;
for(int i = 2;i <= n; ++i){
if(nowk >= 1 && check(i+1,ans|a[i],nowk-1) == mx){
cout<<'|';
ans |= a[i];
nowk--;
}
else cout<<'&',ans &= a[i];
}
}
T4 跳舞
\(solution:\)
用\(ok_{i,j}\)表示\(i\sim j\)可以消去，利用区间dp
\[ok_{i,j} = \max ok_{i,k-1}\& ok_{k+1,j}\&[gcd(a[i-1],a[k])>1\,||\, gcd(a[k],a[j+1])>1] \]再考虑设\(f_i\)表示钦定留下第\(i\)个，可以删掉几个人
则有
\[f_i = \max f_j + ((i-j-1)\&ok_{j+1,i-1}) \]注意处理ok的边界，\(ok_{i,i-1}=1\)
\(code:\)
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
const int N = 510;
bitset<N> ok[N];
int n,a[N],f[N];
bitset<N> gcd[N];
signed main(){
#ifndef ONLINE_JUDGE
infile("in.in");outfile("out.out");
#else
#endif
cin.tie(0)->sync_with_stdio(false);
cout.tie(0)->sync_with_stdio(false);
cin >> n;
for(int i = 1;i <= n; ++i) cin >> a[i];
for(int i = 1;i <= n; ++i)
for(int j = 1;j <= n; ++j)
gcd[i][j] = (__gcd(a[i],a[j])>1);
for(int i = 1;i <= n; ++i)
if(gcd[i][i-1] || gcd[i][i+1]) ok[i][i] = true;
for(int i = 1;i <= n; ++i){
for(int j = 1;j < i; ++j){
ok[i][j] = true;
}
}
for(int len = 2;len <= n; ++len){
for(int i = 1;i + len - 1 <= n; ++i){
int ed = i + len - 1;
for(int j = i;j <= ed; ++j){
if(ok[i][ed]) break;
ok[i][ed] = (ok[i][j-1]&&ok[j+1][ed]&&(gcd[j][i-1]||gcd[j][ed+1]));
}
}
}
for(int i = 2;i <= n+1; ++i){
for(int j = 0; j < i; ++j){
f[i] = max(f[i],f[j]+(i-j-1)*ok[j+1][i-1]);
}
}
cout<<f[n+1];
}
T5 音乐播放器
概率dp，不会……,待填
总结：
还是