D
给定一个长度为 \(n\) 的序列，有如下三种操作：
- 把所有的数全部修改为 \(x\)
- 把第 \(i\) 个数加 \(x\)
- 输出第 \(i\) 个数的值
不难发现，每次一操作会覆盖之前的所有操作，所以只需要最近的一次一操作之后当前数的变化情况即可。
可以用一个栈记录一下。
点击查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,q,a[N],rec[N],add[N],tp=0,base=-1;
signed main()
{
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
cin>>q;
while(q--)
{
int opt,i,x;cin>>opt;
if(opt==1)
{
cin>>x;
base=x;
for(int i=1;i<=tp;++i)
add[rec[i]]=0;
tp=0;
}
else if(opt==2)
{
cin>>i>>x;
add[i]+=x;
rec[++tp]=i;
}
else
{
cin>>i;
if(base==-1)cout<<a[i]+add[i]<<endl;
else cout<<base+add[i]<<endl;
}
}
return 0;
}
E
区间问题，不难想到二维前缀和。
设 \(f[i][j][k]\) 表示 \((1,1)\) 到 \((i,j)\) 区间内 \(k\) 的个数。每次操作可以快速的求出 当前被覆盖的矩形中每一个数的个数，进而求出每一个数的个数。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N=305;
int h,w,n,a,b;
int mp[N][N],f[N][N][N];
int cover(int x,int y,int xx,int yy,int col)
{
return f[xx][yy][col]-f[xx][y-1][col]-f[x-1][yy][col]+f[x-1][y-1][col];
}
signed main()
{
cin>>h>>w>>n>>a>>b;
for(int i=1;i<=h;++i)
for(int j=1;j<=w;++j)
cin>>mp[i][j];
for(int i=1;i<=n;++i)
{
for(int j=1;j<=h;++j)
for(int k=1;k<=w;++k)
{
f[j][k][i]=f[j-1][k][i]+f[j][k-1][i]-f[j-1][k-1][i]+(mp[j][k]==i);
}
}
for(int i=1;i<=h-a+1;++i)
{
for(int j=1;j<=w-b+1;++j)
{
int cnt=0;
for(int k=1;k<=n;++k)
{
int cur=f[h][w][k];
cur-=cover(i,j,i+a-1,j+b-1,k);
if(cur)cnt++;
}
cout<<cnt<<" ";
}
cout<<endl;
}
return 0;
}
F
状压博弈 dp。
设 \(f[S][i]\) 表示已选的单词的状态压缩为 \(S\)，当前词链以 \(i\) 结尾，是否能赢。
转移枚举当前词即可。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N=17;
int n;
string s[N];
bool f[65537][29];
int main()
{
cin>>n;int mx=(1<<n)-1;
for(int i=0;i<n;++i)cin>>s[i];
for(int i=0;i<=mx;++i)
{
for(int j=0;j<n;++j)
if(i&(1<<j))
f[i][s[j][s[j].size()-1]-'a']|=(!f[i-(1<<j)][s[j][0]-'a']);
}
bool ans=0;
for(int i=0;i<n;++i)
ans|=f[mx][s[i][s[i].size()-1]-'a'];
if(ans)puts("First");
else puts("Second");
return 0;
}