D

给定一个长度为 \(n\) 的序列，有如下三种操作：

  1. 把所有的数全部修改为 \(x\)
  2. 把第 \(i\) 个数加 \(x\)
  3. 输出第 \(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;
}

原文地址：http://www.cnblogs.com/lnwhl/p/16909344.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性