A.Love Story
题目翻译
给出一个长度为 $10$ 的字符串，一位一位看问它与
codeforces差了多少字符。$t$ 组数据，$1\leq t\leq 1000$。
题目思路
按照题意模拟，扫描一遍给出字符串，判断第 $i$ 位与 codeforces 的第 $i$ 位是否相同即可。
完整代码
#include<bits/stdc++.h>
using namespace std;
const string t="codeforces";
void solve()
{
string s;
int ans=0;
cin>>s;
for(int i=0;i<10;i++)
{
if(s[i]!=t[i])
{
ans++;
}
}
cout<<ans<<endl;
}
int main()
{
int t;cin>>t;while(t--)
solve();
return 0;
}B.Blank Space
题目翻译
给出一个长度为 $n$ 的序列 $a$，问最长连续 $0$ 有多长。
$1\leq n\leq 100,0\leq a_i\leq 1$。
$t$ 组数据，$1\leq t\leq 1000$。
题目思路
我们遇到一个 $0$，便把长度加上 $1$。如果当前位不是 $0$，说明已经有了一段连续 $0$ 了，计算答案 $ans=\max\{ans,len\}$。
注意循环结束也要计算一遍，防止最后一个是 $0$ 的情况不会统计长度。
完整代码
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin>>n;
int len=0,ans=0;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
if(x!=0)
{
ans=max(ans,len);
len=0;
}
else
{
len++;
}
}
ans=max(ans,len);
cout<<ans<<endl;
}
int main()
{
int t;cin>>t;while(t--)
solve();
return 0;
}C.Mr. Perfectly Fine
题目翻译
有 $n$ 本书，每本书耗时 $a_i$。有一个长度为 $2$ 的字符串 $skill$，$skill_j$ 为 $\tt{1/0}$ 时表示是否获得了第 $j$ 种技能。问最少耗时多久才能学习所有技能。无解输出 $-1$。
$n\leq 2\times 10^5,1\leq a_i\leq 2\times 10^5$。
$t$ 组数据，$1\leq t \leq 1000,\sum_{tt=1}^t n\leq 2\times 10^5$。
题目思路
我们分两种情况讨论，第一种是看两本书学习两个技能，第二种是看一本书学习所有技能。对于两种情况，答案取最小值。
完整代码
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin>>n;
int m1,m2,m12;
m1=m2=m12=(1<<29);
while(n--)
{
int x;
string s;
cin>>x>>s;
if(s=="11")
{
m12=min(m12,x);
}
else if(s=="10")
{
m1=min(m1,x);
}
else if(s=="01")
{
m2=min(m2,x);
}
}
cout<<(min(m1+m2,m12)==(1<<29)?-1:min(m1+m2,m12))<<endl;
}
int main()
{
int t;cin>>t;while(t--)
solve();
return 0;
}D.Gold Rush
题目翻译
有一堆含有 $n$ 个石子的石子堆，你每次可以选择大小为 $k$ 的一堆，将其分成 $\frac{k}{3}$ 与 $\frac{2\times k}{3}$ 两堆，问是否可以得到大小为 $m$ 的堆。
$1\leq n,m\leq 10^7$。
$t$ 组数据，$t\leq 1000$。
题目思路
我们通过阅读题面，因为这个 $n$ 是要分成三份然后一堆一份一堆两份，显然可以得到 $n,m$ 只有可以表示为 $n=3^i\times p,m=2^j\times p(0\leq j\leq i,p\geq 0)$ 时，我们才可以分出来。
考虑到 $n,m$ 都很小，我们枚举这个 $i,j$，判断是否可行即可。
完整代码
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n,m,tmp3=1,tmp2;
cin>>n>>m;
for(int i=0;i<=15;i++)
{
tmp2=1;
for(int j=0;j<=i;j++)
{
if(n%tmp3==0&&n/tmp3*tmp2==m)
{
puts("YES");
return;
}
tmp2*=2;
}
tmp3*=3;
}
puts("NO");
}
int main()
{
int t;cin>>t;while(t--)
solve();
return 0;
}E.The Lakes
题目翻译
你有一个 $n\times m$ 的矩阵，其中有水坑，水坑的大小为 $a_{i,j}$。若 $a_{i,j}=0$ 则不是水坑。问最大的连续水坑大小是多少。
$1\leq n,m\leq 1000,0\leq a_{i,j}\leq 1000$。
$t$ 组数据，$1\leq t \leq 1000,\sum_{tt=1}^t n\times m\leq 10^6$。
题目思路
典型的四方向连通块，使用搜索，深搜广搜均可。
记录每个水坑是否走过避免回头路。
注意开始遍历的时候要判断当前位置是否为 $0$。
1
2 2
0 1
1 0如果不判断的话会从 $(1,1)$ 开始找到 $(1,2)$ 和 $(2,1)$，但其实这两个点不连通。
完整代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
bool vis[1020][1020];
int a[1020][1020];
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
bool judge(int x,int y)
{
return x>=1&&y>=1&&x<=n&&y<=m&&!vis[x][y]&&a[x][y]>0;
}
int dfs(int x,int y)
{
vis[x][y]=1;
int ans=a[x][y];
for(int i=0;i<4;i++)
{
if(judge(x+dx[i],y+dy[i]))
{
ans+=dfs(x+dx[i],y+dy[i]);
}
}
return ans;
}
void solve()
{
cin>>n>>m;
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(!vis[i][j]&&a[i][j])
{
ans=max(ans,dfs(i,j));
}
}
}
cout<<ans<<endl;
}
int main()
{
int t;cin>>t;while(t--)
solve();
return 0;
}F.Forever Winter
题目翻译
我们定义大小 $(x,y)$ 的雪花图表示有一个节点 $u$ 连向 $x$ 个节点，这 $x$ 个节点又分别连向不同于 $u$ 的 $y$ 个节点。给定一张 $n$ 节点 $m$ 条边的雪花图，问这张雪花图的大小是什么。
例如
就是大小为 $(5,3)$ 的雪花图。
$1\leq n\leq 200,1\leq m\leq \min(\frac{n\times (n-1)}{2},1000)$。
题目思路
因为给出的图一定是雪花图，所以我们只需枚举它的大小。然后我们观察样例可得，我们需要有一个度数为 $x$ 的点以及 $x$ 个度数为 $y+1$ 的点（因为连到了 $x$ 个点，每个点还会往中心连一次）。
但仅仅这些还不够，我们需要判断这个 $(x,y)$ 是否满足有 $n$ 个点，即 $x\times y+1=n$。
完整代码
#include<bits/stdc++.h>
using namespace std;
int deg[220];
void solve()
{
memset(deg,0,sizeof(deg));
int n,m;
cin>>n>>m;
while(m--)
{
int u,v;
cin>>u>>v;
deg[u]++;deg[v]++;
}
for(int x=1;x<=200;x++)
{
for(int y=1;y<=200;y++)
{
if(x*(y+1)+1!=n)continue;
int sx=0,sy1=0;
for(int i=1;i<=n;i++)
{
if(deg[i]==x&&!sx){sx=1;continue;}
if(deg[i]==y+1){sy1++;}
}
if(sx==1&&sy1==x)
{
cout<<x<<" "<<y<<endl;
return;
}
}
}
}
int main()
{
int t;cin>>t;while(t--)
solve();
return 0;
}G.Hits Different
题目翻译
你有一个罐子搭成的金字塔，如图
。第 $i$ 个罐子代表数 $i^2$，现在打掉第 $i$ 个罐子，问掉落罐子的数之和为多少。
$1\leq n\leq 10^6$。
$t$ 组数据，$1\leq t\leq 1000$。
题目思路
观察可得，打掉第 $x$ 行第 $y$ 列的罐子，那么第 $x$ 行第 $y-1$ 和第 $x$ 行第 $y$ 列的罐子都会倒塌，然后逐个往上。
我们做一个预处理，只需找出 $n$ 罐子的位置，一个个往上递推，用前缀和优化记录某一行某一段的和即可。
完整代码
#include<bits/stdc++.h>
using namespace std;
int x,l,r;
long long a[2020][2020],cnt;
long long s[2020][2020];
pair<int,int>fa[3000020];
long long Sum(int i,int l,int r)
{
if(l<1)l=1;
if(r>i)r=i;
return s[i][r]-s[i][l-1];
}
void Get(int n)
{
x=fa[n].first;
l=r=fa[n].second;
}
void solve()
{
int n;
long long ans=0;
cin>>n;
Get(n);
while(x>0)
{
ans+=Sum(x,l,r);
l--;
x--;
}
cout<<ans<<endl;
}
int main()
{
for(int i=1;i<=2000;i++)
{
for(int j=1;j<=i;j++)
{
a[i][j]=++cnt;
s[i][j]=s[i][j-1]+a[i][j]*a[i][j];
fa[cnt]=make_pair(i,j);
}
}
int t;cin>>t;while(t--)
solve();
return 0;
}H.Don't Blame Me
题目翻译
你有一个长度为 $n$ 的数组 $a$，问有多少子序列使得选中数字按位与结果中含有 $k$ 个 $1$，答案对 $10^9+7$ 取模。
$1\leq n\leq 2\times 10^5,0\leq k\leq 6,0\leq a_i\leq 63$。
$t$ 组数据，$1\leq t\leq 10^4$。
题目思路
这题非常像背包，但是背包的转移是 f[j]=max(f[j],f[j+w[i]]+value[i]);，这题只不过是把所谓体积的转移从加法改成按位与。
这题 dp 的初值也很有意思，赛时因为最开始的初值赋错导致痛失 AK。
初值应该写成 f[63]=1，假设先放上一个 $(111111)_2$ 去做按位与。因为 $0$ 按位与答案一定是 $0$，后面就没意义了。
但是这样有个问题，当 $k=6$ 因为加了一个额外的 $(111111)_2$，所以会选择空集。$k=6$ 我们最后答案减一即可。
完整代码
#include<bits/stdc++.h>
using namespace std;
const int p=1000000007;
void solve()
{
int n,m;
long long ANS=0;
cin>>n>>m;
int a[n+1];
long long f[64]={},ans[64]={};
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
ans[63]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<64;j++)
{
f[a[i]&j]=(f[a[i]&j]+ans[j])%p;
}
for(int j=0;j<64;j++)
{
ans[j]+=f[j];
f[j]=0;
}
}
for(int i=0;i<64;i++)
{
if(__builtin_popcount(i)==m)
{
ANS=(ANS+ans[i])%p;
}
}
cout<<ANS-(m==6)<<endl;
}
int main()
{
int t;cin>>t;while(t--)
solve();
return 0;
}