Codeforces Round #816 (Div. 2)

总体难度除了AB题之外，其他的题几乎不可做。但是B题出现的问题太大了，WA了五次。最开始的思路没有直接去实现，因为感觉实现不了，最后发现自己写的n+k的复杂度根本过不去。回过头来又考虑的n+计算的思路。

A题：规律题，大意是给出一个n*m的矩阵，a位置（1，1），b位置（n，1），a需要走到右下角，b需要走到右上角。当a走到b走过的路时，可以直接一步走到任意b走过的位置，b同理。求总共最少需要多少步。

我们先让b走到右上角，考虑n和m的大小，令a走一个最小的数量转移到b。

code：

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
inline int read()
{
	int 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-48;ch=getchar();}
	return x*f;
}
void solve()
{
	int n,m;
	cin>>n>>m;
	if(n==1&&m==1) cout<<0<<endl;
	else
	cout<<(m+n-2)+min(n,m)<<endl;
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

B题：大意是给出n，k，b，s。n为长度为a的数组，对于每一个ai，我们使得ai/k 向下取整的总和等于b，且ai的总和等于s。构造这么一组数据，多组可任意，没有输出-1。

很明显的我们可以从大到小考虑，但在这之前我认为应该先想好什么情况下不可能。首先，和的下限一定是k*b，上限一定是k*b+(n)*(k-1)。那么不合法条件就是下限大于s，上限小于s。ok，剩下的我们可以从大到小贪心地去考虑每一个数，我们尽量使得前一个数更大以给后面的数留出更少的分配量，直到数据构造完毕。

code：

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
inline int read()
{
	int 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-48;ch=getchar();}
	return x*f;
}
void solve()
{
	ll n,k,b,s;
	scanf("%lld%lld%lld%lld",&n,&k,&b,&s);
	ll sum = s;
	if(k*b>s) cout<<-1<<endl;
	else if(k*b+n*(k-1)<s) cout<<-1<<endl;
	else
	{
		if(sum-k*b<k) printf("%lld ",sum),sum=0;
		else printf("%lld ",k*b+k-1),sum-=k*b+k-1;
		for(int i=2;i<=n;i++)
		{
			if(sum>=k-1) printf("%lld ",k-1),sum -=k-1;
			else printf("%lld ",sum),sum = 0; 
		}
		cout<<endl;
	}
}
int main()
{
//	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

C题：大意是给出一个数组ai，根据连续情况，我们设置ans。

例如 3,2,2,2,5,4,4 ，对应s 为 1,2,2,2,3,4,4 ，我们要求的答案是对于从1-n开头的s相加。即 1+2+2+2+3+4+4为第一轮，1+1+1+2+3+3 为第二轮，以此轮推。每次操作给出i和x，替换ai为x。然后求出新的答案

我们可以预先求出ans为1开头情况下。然后+上n*(n-1) /2 就是最终答案。在这里有种感觉会是一个等差数列，因为我们把影响因子已经预先求出了。
之后每次查询，我们将两边的影响因子去掉，替换新的数后再增加影响因子。最后计算。

蛮不错的一个技巧题，技巧性很高，idea很难让人想到。

code：

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
inline int read()
{
	int 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-48;ch=getchar();}
	return x*f;
}
void solve()
{
	ll n,m;
	n=read(),m=read();
	vector<int> a(n+2,0);
	for(int i=1;i<=n;i++) a[i] = read();
	ll ans = 0;
	for(int i=1;i<=n;i++) ans+=(a[i]!=a[i+1]) * (n-i)*i;//后面的都会+1 
	while(m--)
	{
		ll i ,x;
		i=read(),x=read();
		ans-=(a[i]!=a[i-1])*(n-i+1)*(i-1);//减去后面的影响
		ans-=(a[i]!=a[i+1])*(n-i)*i;//减去左边的影响
		a[i] = x;
		ans+=(a[i]!=a[i-1])*(n-i+1)*(i-1);//加上后面的影响
		ans+=(a[i]!=a[i+1])*(n-i)*i;//加上左边的影响
		cout<<ans+n*(n+1)/2<<endl;
	}
}
int main()
{
//	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	solve();
}

搜索

标签

存档