B.#15656 游乐园 / AT_abc216_e Amusement Park

题意

高桥君去游乐园玩了。

这个游乐园里有 $N$ 个游乐设施，第 $i$ 个游乐设施的“乐趣”初始值为 $A_i$。当高桥君乘坐第 $i$ 个游乐设施时，会依次发生以下现象：

• 高桥君的“满足度”会增加第 $i$ 个游乐设施当前的“乐趣”值。
• 第 $i$ 个游乐设施的“乐趣”值减少 $1$。

高桥君的“满足度”初始值为 $0$。高桥君最多可以乘坐游乐设施 $K$ 次。 请问高桥君最终能获得的“满足度”的最大值是多少？

注意，高桥君的“满足度”只会因为乘坐游乐设施而变化。

$1\le N\le 10^5$，$1\le K\le 2\times 10^9$，$1\le A_i\le 2\times 10^9$。

思路

想着用堆维护 $k$ 次最优游乐设施，显然超时。这 $k$ 真是大得离谱了。

我们考虑高桥玩的特征：玩满足度最大的。有可能有若干个满足度都是最大的，设从大到小排列 $a_{\mathrm{1...}m}$ 是 $m$ 个最优项目，那么高桥会在 $m$ 个之间交替游玩，直到这 $m$ 个项目满足度降到 $a_{m+1}$，然后又在 $m+1$ 个之间交替游玩……

那么枚举 $i\in [1,n]$ 不仅是项目下标，还是交替游玩的项目数，对于前 $i$ 项游玩 $i\times (a_i-a_{i+1})$ 次。这显然是最优方案，记 $d=a_i-a_{i+1}$，当交替游玩 $i$ 个项目为答案贡献了 $i\times \sum _{t=a_{i+1}+1}^{a_i}t=\frac{id(a_{i+1}+1+a_i)}{2}$，用到了等差数列求和公式，次数记得减去 $i\times d$。

如果剩下的次数不够交替玩 $i\times d$ 次，那就以玩 $i$ 次为周期，玩 $cnt=\lfloor k/i\rfloor$ 个周期，余数 $ys=k-cnt\times i$ 也用来玩 $ys$ 次满足度为 $a_i-cnt$ 的项目。依然等差数列求和。具体细节见代码。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e5+9;
ll n,k;
ll a[N];
bool cmp(ll x,ll y)
{
	return x>y; 
}
int main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++)
	scanf("%lld",&a[i]);
	sort(a+1,a+n+1,cmp);
	ll ans=0;
	for(int i=1;i<=n;i++)//交替游玩项目数 
	{
		ll d=a[i]-a[i+1];//a[i]前全部交替游玩，直到玩到a[i+1] 
		k-=d*i;
		if(k<0)
		{
			k+=d*i;
			ll cnt=k/i,ys=k%i;
			ans+=i*(a[i]+a[i]-cnt+1)*cnt/2+ys*(a[i]-cnt);//用不完全部 
			break;
		}
		ans+=i*(a[i+1]+1+a[i])*d/2;
		//首项 a[i+1]+1 末项a[i] 
	}
	printf("%lld",ans);
	return 0;
}

C.#16007 抽卡

题意

思路

模拟题而已，考察 STL 的应用。用 set 维护堆顶以及 upper_bound 查询操作，map 套 vector 维护每个牌堆堆顶和牌，因为 map 和 vector 这些 STL 非常灵活，可以用 move() 实现数据的迁移和 erase 实现删除。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+9;
int n,k;
set<int>S;//堆顶 
map<int,vector<int> >heap;//堆顶与堆 
int ans[N];
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		set<int>::iterator it=S.upper_bound(x);
		if(it==S.end())
		{
			if(k==1)
			{
				ans[x]=i;
				continue;
			}
			S.insert(x);
			heap[x].push_back(x);
		}
		else 
		{
			int lastop=*it;
			S.erase(lastop);
			vector<int>&tem=heap[lastop];//防止每次开一个vector，不然会 MLE
			tem.push_back(x);
			if(tem.size()==k)
			{
				for(auto t:tem)
				ans[t]=i;
				heap.erase(lastop);
			}
			else 
			{
				S.insert(x);
				heap[x]=move(tem);
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(ans[i]==0)puts("-1");
		else printf("%d\n",ans[i]);
	}
	return 0;
}

D.#16016 位运算操作 / AT_abc261_e Many Operations

题意

有一个变量 $X$，以及 $N$ 种可以改变 $X$ 值的操作。第 $i$ 个操作由整数对 $(T_i,A_i)$ 表示，含义如下：

• 当 $T_i=1$ 时，将 $X$ 的值替换为 $X\mathrm{and}{A}_i$。
• 当 $T_i=2$ 时，将 $X$ 的值替换为 $X\mathrm{or}{A}_i$。
• 当 $T_i=3$ 时，将 $X$ 的值替换为 $X\mathrm{xor}{A}_i$。

请从变量 $X$ 被初始化为值 $C$ 的状态开始，依次执行以下操作：

• 执行操作 $1$，输出操作后的 $X$ 的值。
• 接着，依次执行操作 $1,2$，输出操作后的 $X$ 的值。
• 接着，依次执行操作 $1,2,3$，输出操作后的 $X$ 的值。
• $⋮$
• 接着，依次执行操作 $1,2,\dots ,N$，输出操作后的 $X$ 的值。

$1\le N\le 2\times 10^5$，$1\le T_i\le 3$，$0\le A_i<2^{30}$，$0\le C<2^{30}$。

思路

操作次数超级多，而且位运算没有交换律。

看到范围，$C,A_i$ 再大二进制顶天就 $30$ 位，于是考虑拆位计算每一位。

三种运算都有一些性质，对于一个二进制位 x ∈ { 0 , 1 } x\in\{0,1\} x∈{0,1}：

• $x\mathrm{and}0=0$，$x\mathrm{and}1$ 无事发生；
• $x\mathrm{or}1=1$，$x\mathrm{or}0$ 无事发生；
• $x\mathrm{xor}0$ 无事发生，$x\mathrm{xor}1$ 就反转。

枚举二进制位 $t\in [0,30]$，记 $cur$ 为当前 $C$ 的 $t$ 位。枚举 $i$ 表示以第 $i$ 次操作结尾，记 $x$ 位 $a_i$ 的 $t$ 位。

• 当 $op=1$ 为 $\mathrm{and}$ 操作，若 $x=0$ 则每到这次操作 $t$ 位都变成 $alt=0$；
• 当 $op=2$ 为 $\mathrm{or}$ 操作，若 $x=1$ 则每到这次操作 $t$ 位都变成 $alt=1$；
• 当 $op=3$ 位 $\mathrm{xor}$ 操作，若 $x=1$ 则每到这次操作都要数位反转，$xortot+1$。

上文的 $alt$ 和 $xortot$ 相当于两个 $tag$，虽然以第 $i$ 步结尾，前面还有很多步没看，但是做到这步答案都是固定的——不论前面的操作如何，做到这步，该位必然是 $alt$。

初始时 $alt=-1$，如果 $alt$ 没有被修改就不管它，表示前面没有可以影响 $cur$ 的 $op=1/2$ 操作；否则直接把 $alt$ 赋值到 $cur$ 上。

如果 $xortot$ 为奇数，说明 $cur$ 位要被反转。同时反转后不清空 $xortot$，因为后面的某一个结尾出现 $\mathrm{xor}1$ 时，前面被反转了奇数次，加上这次就偶数次，相当于没影响。

然后根据 $cur$ 是否为 $1$ 为 $an{s}_i$ 的 $t$ 位决定填 $1$ 还是填 $0$，$an{s}_i$ 表示以操作 $i$ 为结尾的答案。

感觉这个做法很神仙（玄学）！这种奇妙的更新题也就 AT 能出了 qwq。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2e5+9;
ll n,c;
ll op[N],a[N];
ll ans[N];
int main()
{
	scanf("%lld%lld",&n,&c);
	for(int i=1;i<=n;i++)
	scanf("%lld%lld",&op[i],&a[i]);
	for(ll t=30;t>=0;t--)
	{
		bool cur=(c&(1<<t));
		ll alt=-1,xortot=0;
		for(ll i=1;i<=n;i++)//第i操作结尾 
		{
			bool x=(a[i]&(1<<t));//做到这步，该位必然是alt
			if(op[i]==1){cur&=x;if(x==0)alt=x,xortot=0;}
			if(op[i]==2){cur|=x;if(x==1)alt=x,xortot=0;}
			if(op[i]==3)xortot+=x;
			if(alt!=-1)cur=alt;//不论前面的操作如何，到这里都是alt 
			if(xortot&1)cur^=1;
			if(cur)ans[i]+=(1<<t);
		}
	}
	for(int i=1;i<=n;i++)
	printf("%lld\n",ans[i]);
	return 0;
}

E.#16313 纵横权重和 / AT_abc298_f Rook Score

我的博客

F.#9160 写诗 / 洛谷 P5196 USACO19JAN Cow Poetry G

题意

题目传送门，建议去仔细读懂题意和样例解释。

思路

音节即长度。因为韵部只是对一串单词的最后一个有要求，前面可以乱排。设 $g_i$ 表示乱排组成 $i$ 个音节的方案数，容易递推转移：

g[0]=1;//初始化
for(int i=1;i<=k;i++)
for(int j=1;j<=n;j++)//单词下标 
if(i>=len[j])g[i]=(g[i]+g[i-len[j]])%mod;

（此处是乱排，词语顺序改变算作不同方案，故先枚举背包，不计算顺序变化详见这里）

单词有 $n$ 个，韵部最多 $n$ 种，我们用 $n$ 个动态数组 $Y_i$ 存储韵部为 $i$ 的单词长度集合。设 $f_i$ 表示韵脚为 $i$ 的方案数，枚举韵脚 $i$，对于一个韵部为 $i$、长度为 $len$ 的单词：
$$f_i\leftarrow g_{k-len}$$

规定的那个模式串其实没什么用，只需要统计每个字母的个数 $cn{t}_i$，$i\in [A(1),Z(26)]$。分别枚举押韵模式和韵脚，使二者配对，然后计算 $\sum _{i=1}^{26}\sum _{j=1}^n{f}_j^{cn{t}_i}$ 即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5009,mod=1e9+7;
int n,m,k;
int len[N],yun[N];
char e[N];
ll f[N],g[N];
//f(y):韵脚为y方案数 
//g(i):i个音节方案数 
int cnt[33];
ll qpow(ll x,ll k)
{
	ll ret=1;
	while(k)
	{
		if(k&1)ret=ret*x%mod;
		x=x*x%mod;
		k>>=1;
	}
	return ret;
}
vector<ll>Y[N];
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&len[i],&yun[i]);
		Y[yun[i]].push_back(len[i]);
	}
	g[0]=1;
	for(int i=1;i<=k;i++)
	for(int j=1;j<=n;j++)//单词下标 
	if(i>=len[j])g[i]=(g[i]+g[i-len[j]])%mod;
	for(int i=1;i<=n;i++)//韵脚 
	for(auto x:Y[i])
	f[i]=(f[i]+g[k-x])%mod;//前面单词乱拍，最后一个制定韵脚为i 
	for(int i=1;i<=m;i++)
	{
		char c;
		cin>>c;
		cnt[c-'A'+1]++;
	}
	ll ans=1;
	for(int i=1;i<=26;i++)//单句的模式 
	{
		if(!cnt[i])continue; 
		ll sum=0;
		for(int j=1;j<=n;j++)//韵部 
		sum=(sum+qpow(f[j],cnt[i]))%mod;
		ans=ans*sum%mod;
	}
	printf("%lld",ans);
	return 0;
}

G.#9171 涂抹油漆 / 洛谷 P6100 USACO19FEB Painting the Barn G

题意

我们将谷仓的墙描述为一个 X-Y 平面，每次涂油漆的区域都是一个矩形。FJ 在这个平面上绘制了 $N$ 个矩形，每个矩形的边均与坐标轴平行。因此我们用矩形的左下角和右上角坐标来描述一个矩形。

FJ 想在谷仓里涂几层油漆，这样就不需要在不久的将来再次重新涂油漆。但是，他不想浪费时间涂过多的油漆。事实证明，$K$ 层涂料是最佳用量。但是因为涂油漆的面积太小了，FJ 并不太高兴。他决定最多再绘制两个不相交的矩形（这里的相交指两个矩形交的面积大于零，即如果两个矩形仅共用一条边或一个点，则不视为相交）来增加面积。当然不绘制新矩形或仅绘制一个新矩形也是允许的。

$1\le N,K\le 10^5$，$0\le x_1,y_1,x_2,y_2\le 200$。

思路

只有被涂了 $k-1$ 和 $k$ 次的矩形会影响贡献。根据本题弱化版我们使用二维查分计算每个格子被涂了几次（代码坐标 $+1$ 避开 $0$）：

for(int i=1;i<=n;i++)
{
	ll xa,ya,xb,yb;
	scanf("%lld%lld%lld%lld",&xa,&ya,&xb,&yb);
	a[xa+1][ya+1]++,a[xb+1][yb+1]++;
	a[xb+1][ya+1]--,a[xa+1][yb+1]--;
}
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];

在已经填了 $k-1$ 次的格子上再涂抹会产生 $+1$ 贡献；在已经填了 $k$ 次的格子上再涂抹会产生 $-1$ 贡献。

设 $f_{i,j}$ 表示以 $(i,j)$ 为右下角的最大贡献，$g_{i,j}$ 表示以 $(i,j)$ 为左上角的最大贡献。那么我们要找一个包含 $(i,j)$ 的子矩阵。

子矩阵问题考虑枚举行或者列的上下界，然后压成一个一维数组找，计算当前 $a_{x,ij}$ 的前缀和 $s_x$，记 $s$ 数组的前缀最小值 $mn$，那么 f x , j = max ⁡ { s x − m n } f_{x,j}=\max\{s_x-mn\} fx,j​=max{sx​−mn}；反过来处理 $g_{x,i}$ 同理。下面的枚举了列的上下界（也不记得为什么了，本人的习惯是枚举行的上下界）。

memset(f,-inf,sizeof(f));//不能只赋0
memset(g,-inf,sizeof(g));
for(int i=1;i<=N;i++)
{
	for(int j=i;j<=N;j++)
	{
		ll mn=0;
		for(int x=1;x<=N;x++)
		{
			s[x]=s[x-1]+cal(x,i,x,j);
			f[x][j]=max(f[x][j],s[x]-mn);
			mn=min(s[x],mn);
		}
		mn=0;
		for(int x=N;x>=1;x--)
		{
			s[x]=s[x+1]+cal(x,i,x,j);
			g[x][i]=max(g[x][i],s[x]-mn);
			mn=min(s[x],mn);
		}
	}
}

最后计算 $(1,1)-(i,j)$ 内的最大贡献矩形 $F_{i,j}$ 和 $(i,j)-(n,m)$ 内的最大贡献矩形 $G_{i,j}$。然后枚举将矩形分开两部分的直线 $x=i$ 或者 $y=i$，计算 max ⁡ ( max ⁡ { y = i ∣ F N , i − 1 + G 1 , i } , max ⁡ { x = i ∣ F i − 1 , N + G i , 1 } ) \max(\max\{y=i|F_{N,i-1+G_{1,i}}\},\max\{x=i|F_{i-1,N}+G_{i,1}\}) max(max{y=i∣FN,i−1+G1,i​​},max{x=i∣Fi−1,N​+Gi,1​})。

代码

//for test
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=200,inf=0x3f3f3f3f;
ll n,k;
ll a[N+3][N+3],b[N+3][N+3],sum[N+3][N+3],s[N+3];
ll f[N+3][N+3],g[N+3][N+3],F[N+3][N+3],G[N+3][N+3];
ll cntk,ans;
ll cal(ll xa,ll ya,ll xb,ll yb)
{
	return sum[xb][yb]-sum[xa-1][yb]-sum[xb][ya-1]+sum[xa-1][ya-1];
}
int main()
{
//	freopen("P6100_2.in","r",stdin);
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++)
	{
		ll xa,ya,xb,yb;
		scanf("%lld%lld%lld%lld",&xa,&ya,&xb,&yb);
		a[xa+1][ya+1]++,a[xb+1][yb+1]++;
		a[xb+1][ya+1]--,a[xa+1][yb+1]--;
	}
	for(int i=1;i<=N;i++)
	for(int j=1;j<=N;j++)
	sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=N;j++)
		{
			if(sum[i][j]==k-1)a[i][j]=1;
			else if(sum[i][j]==k)cntk++,a[i][j]=-1;
			else a[i][j]=0;
		}
	}
	for(int i=1;i<=N;i++)
	for(int j=1;j<=N;j++)
	sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
	memset(f,-inf,sizeof(f));
	memset(g,-inf,sizeof(g));
	for(int i=1;i<=N;i++)
	{
		for(int j=i;j<=N;j++)
		{
			ll mn=0;
			for(int x=1;x<=N;x++)
			{
				s[x]=s[x-1]+cal(x,i,x,j);
				f[x][j]=max(f[x][j],s[x]-mn);
				mn=min(s[x],mn);
			}
			mn=0;
			for(int x=N;x>=1;x--)
			{
				s[x]=s[x+1]+cal(x,i,x,j);
				g[x][i]=max(g[x][i],s[x]-mn);
				mn=min(s[x],mn);
			}
		}
	}
	memset(F,-inf,sizeof(F));
	memset(G,-inf,sizeof(G));
	for(int i=1;i<=N;i++)
	for(int j=1;j<=N;j++)
	F[i][j]=max(max(F[i][j],f[i][j]),max(F[i-1][j],F[i][j-1]));
	for(int i=N;i>=1;i--)
	for(int j=N;j>=1;j--)
	G[i][j]=max(max(G[i][j],g[i][j]),max(G[i+1][j],G[i][j+1]));
	for(int i=2;i<=N;i++)
	ans=max(ans,max(F[N][i-1]+G[1][i],F[i-1][N]+G[i][1]));
	printf("%lld",ans+cntk);
	return 0;
}