The 2021 China Collegiate Programming Contest (Harbin) JBEID
J. Local Minimum 模拟
题意：一个数当且仅当它是当前列最小值同时也是当且行的最小值它才算入贡献。
思路：直接\(for\),预处理出每一行每一列的最小值，然后去\(check\)每一个数。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e3 + 10;
ll minc[N],minr[N],c[N][N],a[N][N];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int n,m;
cin>>n>>m;
ll ans = 0;
for(int i = 1;i <= n; i++)
{
for(int j = 1;j <= m; j++)
{
cin>>a[i][j];
minc[j] = 1e18;
minr[i] = 1e18;
}
}
for(int i = 1;i <= n; i++)
{
for(int j = 1;j <= m; j++)
{
minr[i] = min(minr[i],a[i][j]);
}
}
for(int j = 1;j <= m; j++)
{
for(int i = 1;i <= n; i++)
{
minc[j] = min(minc[j],a[i][j]);
}
}
for(int i = 1;i <= n; i++)
{
for(int j = 1;j <= m; j++)
{
if(a[i][j]==minr[i])
c[i][j]++;
}
}
for(int j = 1;j <= m; j++)
{
for(int i = 1;i <= n; i++)
{
if(a[i][j]==minc[j])
c[i][j]++;
}
}
for(int i = 1;i <= n; i++)
{
for(int j = 1;j <= m; j++)
{
ans += (c[i][j]>=2);
}
}
cout<<ans<<"\n";
return 0;
}
B. Magical Subsequence 前缀+DP
题意：给你一个序列\(A_1,A_2,...,A_n\) ,我们选择该序列的一个子序列\(A_{b_1},A_{b_2},...,A_{b_m}\)。我们说它是有魔法的，当且仅当\(m\)是偶数，且\(A_{b_1}+A_{b_2} = A_{b_3}+A_{b_4}=...=A_{b_{m-1}}+A_{b_m}\)。找出满足条件的最大的子序列长度。
思路：因为\(A_i\)范围只有\(100\)，那么两个数的和只在\(2～200\)之间。那么我们可以枚举两个数的和是多少去\(dp\)。
定义：\(dp[i][sum]\)表示，前\(i\)个两个和为\(sum\)的最长序列是多少。
那么\(dp[i][sum] = max(dp[i][sum],dp[last[j]-1][sum]+2)\)，其中\(last[j]\)表示上一个为\(j\)的数出现在哪(边做边去更新\(last\)数组)，用这个\(j\)和我们当前的\(a[i]\)配对，贡献就是从上一个\(j\)前面的贡献\(+2\)。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e5+10;
int a[N];
int last[N];
int f[N][210];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int n;
cin>>n;
for(int i = 1;i <= n; i++)
cin>>a[i];
for(int i = 1;i <= n; i++)
{
for(int j = 2;j <= 200; j++)
f[i][j] = max(f[i][j],f[i-1][j]);
for(int j = 1;j <= 100; j++)
{
if(!last[j])continue;
int sum = j+a[i];
//last_num = j,now_num = a[i];
f[i][sum] = max(f[i][sum],f[last[j]-1][sum]+2);
}
last[a[i]] = i;
}
int ans = 0;
for(int i = 1;i <= n; i++)
for(int j = 2;j <= 200; j++)
ans = max(ans,f[i][j]);
cout<<ans<<"\n";
return 0;
}
E. Power and Modulo 思维
题意：给你\(n\)个非负整数\(A_1,A_2,...,A_n\)，问你是否存在有且仅有一个正整数\(M\)，使得\(A_i = 2^{i-1}\bmod M\).如果有就输出\(M\),否则输出\(-1\)。
思路：因为我们知道都是\(2\)的幂次模\(M\),一旦第一个发现小于了它原本应该的数，说明它已经大于\(M\)了。如果要满足题意，那么此时的\(M\)应该为\(mi-a[i]\)。然后去\(check\)这个\(M\)是否满足条件即可。
注意：
- 不能先预处理幂次，因为你无法预处理出\(1e5\)个，那么你应该在得出可能的\(M\)之后，边算边模。
- 一开始的\(1\)也要模\(M\)。
- 如果有\(a[i]>M\)的也不满足。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll a[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i = 1;i <= n; i++)
{
cin>>a[i];
}
ll m = -1;
ll mi = 1;
for(int i = 1;i <= n; i++)
{
if(a[i]!=mi)
{
m = mi-a[i];
break;
}
mi *= 2;
}
if(m==-1)
{
cout<<"-1\n";
continue;
}
bool ok = true;
mi = 1%m;
for(int i = 1;i <= n; i++)
{
//cout<<"mi = "<<mi[i-1]<<"\n";
if((mi%m!=a[i])||a[i]>m)
{
ok = false;
break;
}
mi *= 2;
mi%=m;
}
if(ok)cout<<m<<"\n";
else cout<<-1<<"\n";
}
return 0;
}
I. Power and Zero 二进制+思维
题意：给你一个正整数序列\(A_1,A_2,...,A_n\),你需要进行一些操作把它们都变成\(0\)。每次操作呢，你可以选一些下标，对它们减去\(2\)的幂次\(2^0,2^1,...,2^m\)。问最少的操作次数。
思路：由于每次都是减去一段连续的\(2\)的幂次，最后变为\(0\)。那么我们可以从二进制考虑。一开始我的思路是统计二进制的每一位有多少个，然后全部转化为\(2^0\)的个数，再去计算贡献，但是是错的(不晓得为什么\(QAQ\))。以下是我写的错误代码：
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll a[N],mi[N],sum[N];
ll cnt[100];
void init()
{
ll base = 1;
for(int i = 0; i < 100; i++)
mi[i] = base,base*=2,sum[i+1] = sum[i]+mi[i];
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t;
cin>>t;
init();
while(t--)
{
int n;
cin>>n;
memset(cnt,0,sizeof(cnt));
int mx = 0;
for(int i = 1;i <= n; i++)
cin>>a[i];
for(int i = 1;i <= n; i++)
{
ll x = a[i];
for(int j = 0;j < 64; j++)
{
if((x>>j)&1)
cnt[j]++,mx = max(mx,j+1);
}
}
// for(int i = 0; i < 64; i++)
// cout<<cnt[i]<<" ";
// cout<<"\n";
// cout<<"sum = ";
// for(int i = 0; i < 64; i++)
// cout<<sum[i]<<" ";
// cout<<"\n";
for(int i = 1; i < 64; i++)
{
cnt[0] += cnt[i]*mi[i];
}
// cout<<"cnt = "<<cnt[0]<<" mx = "<<mx<<"\n";
ll t = cnt[0];
ll ans = 0;
while(t)
{
//cout<<"t = "<<t<<"\n";
ll l = 0,r = mx;
while(l<=r)
{
ll mid = (l+r)>>1;
if(sum[mid]<=t)l = mid+1;
else r = mid-1;
}
ll pos = l-1;
ans += t/sum[pos];
t %= sum[pos];
}
cout<<ans<<"\n";
}
return 0;
}
那么正解是什么呢？最后队友写出来了。其实一开始的思路是有道理的。一开始我们也是考虑统计二进制的每一位有多少个，然后一层一层的去减，但是问题出现了：万一不够减怎么办呢？然后我就想可以拿后面的去补上。但是问题又来了，怎么补，用哪个去补？
听了队友的分析，了解到最终一定是调整为一段形如：
\(cnt_0,cnt_1,cnt_2,...,cnt_n\)。其中\(cnt_0,cnt_1,cnt_2,...,cnt_n\)单调递减的(因为这样才能保证是连续的，可以想象成一个类似于梯形的形状，每次减去一层（这样也不会有不够减的情况），才是最优的)。
那么我们从后往前遍历，当发现当前位置的\(1\)的个数大于前面的一个位置了，我们就挪一些(均匀一些)到它的前一个(保证前一个位置个数\(\ge\)当前位置数的个数)。
if(cnt[i-1]<cnt[i])
{
ok = false;
int d = cnt[i]-cnt[i-1];
if(d%3==0)
cnt[i-1]+=d/3*2,cnt[i]-=d/3;
else
cnt[i-1]+=(d/3+1)*2,cnt[i]-=(d/3+1);
}
不断调整(\(O(NlogN)\))，直到是单调递减的为止，同时这样调整是均匀的能保证\(1\)的个数最小化。最后的答案就是调整完之后的\(cnt_0\)。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int cnt[35];
int a[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
memset(cnt,0,sizeof(cnt));
for(int i = 1;i <= n; i++)
cin>>a[i];
for(int i = 1;i <= n; i++)
for(int j = 0;j < 32; j++)
if((a[i]>>j)&1)
cnt[j]++;
while(1)
{
bool ok = true;
for(int i = 32;i >= 1; i--)
{
if(cnt[i-1]<cnt[i])
{
ok = false;
int d = cnt[i]-cnt[i-1];
if(d%3==0)
cnt[i-1]+=d/3*2,cnt[i]-=d/3;
else
cnt[i-1]+=(d/3+1)*2,cnt[i]-=(d/3+1);
}
}
if(ok)break;
}
cout<<cnt[0]<<"\n";
}
return 0;
}
D. Math master 暴力二进制枚举
题意：给你一个分数\(\dfrac{p}{q}\)，当分子和分母都存在某一个数的时候可以把这个数删去(前提是分数值保持不变)。由于\(p,q\)是\(2^{63}\)级别的，那么对应十进制只有\(19\)位。我们可以考虑暴力枚举分子\(p\)化为最简是什么，假设是\(a\)，那么分子应该相应为\(b = aq/p\)。然后我们只要去\(check(b)\)，找到满足条件的最小的一组\(a,b\)。
对于\(check\)，看看\(q\)需要删除什么会得到\(b\)，然后去比较看看\(cnta\)和\(cntb\)是不是完全一样即可。
特别要小心和注意的是\(a\ne0,b\ne0,a*q\%p==0\),还有记得开\(int128\)
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int __int128
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
//2^63 = 9223372036854775808
//19位数
int cnta[10],cntb[10];
int sz1,sz2;
string sp,sq;
inline __int128 read(){__int128 x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
inline void write(__int128 x){if (x < 0){putchar('-');x = -x;}if (x > 9) write(x / 10);putchar(x % 10 + '0');}
bool check(ll b)
{
for(int i = sz2-1;i >= 0; i--)
{
if(sq[i]-'0'==b%10)
b/=10;
else cntb[sq[i]-'0']++;
}
if(b)return false;//说明全删了，肯定是不行的
for(int i = 0;i <= 9; i++)
if(cnta[i]!=cntb[i])return false;
return true;
}
signed main()
{
//ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int n;
n = read();
for(int i = 1;i <= n; i++)
{
cin>>sp>>sq;
sz1 = sp.size(),sz2 = sq.size();
int p = 0,q = 0;
for(int i=0;i<sz1;++i) p=p*10ll+(sp[i]-'0');
for(int i=0;i<sz2;++i) q=q*10ll+(sq[i]-'0');
ll ansa = p,ansb = q;
/*
p/q = a/b;
b = aq/p;
*/
for(int i = 0; i < (1<<sz1); i++)
{
ll a = 0,b = 0;
for(int i = 0;i <= 9;i++)
cnta[i] = cntb[i] = 0;
for(int j = 0;j < sz1; j++)
{
if((i>>j)&1)
a*=10ll,a+=sp[j]-'0';
else cnta[sp[j]-'0']++;
}
if(!a||a*q%p)continue;//注意不能为0，且要可aq以被p整除
b = a*q/p;
if(check(b))
ansa = min(ansa,a),ansb = min(ansb,b);
}
write(ansa);cout<<" ";write(ansb);cout<<"\n";
}
return 0;
}
- Programming Collegiate Contest Harbin Chinaprogramming collegiate contest harbin programming collegiate provincial contest programming collegiate jiangsu contest international programming collegiate contest programming collegiate mianyang contest programming collegiate contest guilin programming collegiate shenzhen contest programming collegiate shanghai contest programming collegiate codeforces contest programming collegiate contest weihai