\

前言

没什么好说了。

第一次打CF到1点多。

爆肝!!!

题解

A. Elections

题意

给一个数列a,问最小的k使得$\sum \limits_{i=1}^n(k-a_i) > \sum a_i~(a_i,n\le 100)$。

做法

1# 可以暴力枚举k(数据规模小)

2# 可以算得k=$\lceil\frac{\sum a_i \times 2+1}{n}\rceil$

代码

(不优秀的写法)

#include<bits/stdc++.h>
int a[10000],n,mx;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]),mx=mx>a[i]?mx:a[i];
	int have=0,tot=mx*n;
	for(int i=1;i<=n;i++)
		have+=mx-a[i];
	if(have>tot-have){printf("%d",mx);return 0;}
	int need=(tot-have)-have;
	int more=need/n+(bool)(need%n>0);
	while(have+more*n==(tot-have))more++;
	printf("%d",mx+more);
}

B. Lost Array

题意

有一个原数列$x_0,x_1...x_n$,据x构造出了数列a,$a_0=0,~a_i = x_{(i-1)\bmod k} + a_{i-1}$,现在知道a数列,求可能的x数列长度的种数和长度。

做法

首先易得$a_1=x_0+a_0=x_0$,由此我们可以推出可能的x数列的展开形式$x'_i=a_{i+1}-a_i$,然后就是在a的差分数列上找循环部分了。

代码

#include<bits/stdc++.h>
using namespace std;
list<int>q;
int n,a[10000],b[10000],ans;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		b[i]=a[i]-a[i-1];//b[i]=x[i-1]
	}
	for(int i=1;i<=n;i++)
	{
		bool flag=true;
		for(int j=i+1;j<=n;j++)
		{
			if(b[j]!=b[(j-1)%i+1]){flag=false;break;}
		}
		ans+=flag;
		if(flag)q.push_back(i);
	}
	printf("%d\n",ans);
	for(auto i:q)
		printf("%d ",i);
}

C. Smallest Word

卡了我好久,贪心学得太差劲了。

题意

给出一个由'a','b'组成的字符串,对于第i位的操作会将1...i的子串翻转,求可行翻转方案使得字符串最终字典序最小,即成为'a...ab...b'的形式。

做法

我的垃圾做法:碰到第i和i+1不同时如果这位是a就翻转(真正把子串翻转一遍),并且如果之前的翻转使得第一位为a就将上一次可能的翻转取反;如果是b就不翻转。凡是前后不同处记为可能的翻转。复杂度$O(n^2)$。

别人的优秀做法:不知道怎么发现的规律,我怎么就没发现呢?

(s[i] == 'a' && s[i + 1] == 'b' || s[i] == 'b' && s[i + 1] == 'a')

代码

#include<bits/stdc++.h>
using namespace std;
char str[10000],tmp[10000];
bool rev[10000];
int main()
{
	int lst=0;
	scanf("%s",str);
	int n=strlen(str);
	for(int i=1;i<n;i++)
	{
		if(str[i]==str[i+1]&&str[i]=='a')continue;
		if(str[i]=='a')
		{
			rev[i]=true;
			if(str[0]=='a')rev[lst]^=1;
			for(int j=0;j<=i;j++)tmp[j]=str[j];
			for(int j=0;j<=i;j++)str[i-j]=tmp[j];
			lst=i;
		}
		else rev[i]=false,lst=i;
	}
	//if(str[n-1]=='a')rev[n-1]=true;
	for(int i=0;i<n;i++)putchar(rev[i]+'0'),putchar(' ');
}

D. Mysterious Crime

这题提交RE1遍TLE2遍WA1遍。原因是我看题目里说$m\le10$,就开了第二维是10的数组。。。

题意

给m个长为n的数列,每个数列中每个元素只出现1次,求连续公共子序列的方案。

做法

发现m很小,所以我们以其中任意一个序列为母本,扫一遍,check得到连续的子序列组成的较长的子序列,然后$n\times(n-1)/2$计算方案。具体check过程就是记录每个元素在每个数列中出现的位置,就可以$O(m)$ check每一位。然后while循环跑一跑,算一算就好了。

代码

#include<bits/stdc++.h>
using namespace std;
void read(int &x)
{
	scanf("%d",&x);
}
const int N=100020;
int n,m,a[12][N],appear[N][12];
long long ans;
bool chk(int st,int len)
{
    if(appear[st][1]+len>n)return false;
	int T=a[1][appear[st][1]+len];
	for(int i=2;i<=m;i++)
        if(appear[st][i]+len>n||a[i][appear[st][i]+len]!=T)
        return false;
	return true;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		read(a[i][j]),appear[a[i][j]][i]=j;
	}
	int lst=0;
	for(int i=1,j;i<=n;i++)
	{
		j=0;
		while(chk(a[1][i],j))j++;
		i+=max(j-1,0);
		ans+=(long long)(i-lst)*(i-lst+1)/2;
		lst=i;
	}
	printf("%lld",ans);
}

E. Train Hard, Win Easy

题意

n个人,两两进行一次比赛,每次比赛有2题,一个人只能选其中1题,另一个人则选择另一题,两个人遵循使比赛得分最小的策略。

其中有m对人不会合作(不会在一起比赛),求每个人最终得分(每场得分为两题得分之和)。

数据范围$(2\le n\le300000,0\le m\le300000)$

做法

n,m的范围决定了此题复杂度在$O(nlogn)$左右。

我们分析一下题目选择的贪心策略,若第i个人比第j个人更适合做第1题(记为x),有$$a_i.x+b_j.y\le a_i.y+b_j.x$$变形得到$$a_i.x-a_i.y\le b_j.x-b_j.y$$

我们发现此式具有单调性,因此可以直接sort。

然后对sort后的序列维护前缀和记录前面的人做x,y的得分和分别是多少。

对于每个人二分得到多少人和他配对时他做x,多少人配对时他做y,结合前缀和算得得分总和。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+20;
struct node
{
	long long x,y;
	int id;
	bool operator<(const node& a)const{return (x-y)==(a.x-a.y)?x<a.x:(x-y)<(a.x-a.y);}
}o[N];
list<int>conflict[N];
long long sumx[N],sumy[N],ans[N];
int n,m;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	scanf("%lld%lld",&o[i].x,&o[i].y),o[i].id=i;
	long long dec;
	for(int i=1,xi,yi;i<=m;i++)
	{
		scanf("%d%d",&xi,&yi);
		if((o[xi].x-o[xi].y)<(o[yi].x-o[yi].y))ans[xi]-=o[xi].x,ans[yi]-=o[xi].x,ans[yi]-=o[yi].y,ans[xi]-=o[yi].y;
		else ans[xi]-=o[xi].y,ans[yi]-=o[yi].x,ans[xi]-=o[yi].x,ans[yi]-=o[xi].y;
	}
	sort(o+1,o+1+n);
	for(int i=1;i<=n;i++)sumx[i]=sumx[i-1]+o[i].x,sumy[i]=sumy[i-1]+o[i].y;
	for(int i=1;i<=n;i++)
	{
		int k=lower_bound(o+1,o+1+n,o[i])-o;
		ans[o[i].id]+=(long long)(k-1)*o[i].y+sumx[k-1],ans[o[i].id]+=(long long)(n-k)*o[i].x+sumy[n]-sumy[k];
	}
	for(int i=1;i<=n;i++)
	printf("%lld ",ans[i]);
}

F. Make It One

做法

据说是莫比乌斯反演板子题。。。

留坑待填

G. Speckled Band

做法

据说又是另一道题的加强版多组数据版。

留坑待填

后记

这场Codeforces有点水,然而我用的是惨掉几百分的大号,仅仅重回specialist。要是用新开的小号上分多好啊。

C卡了好久说明我贪心方面的思维确实不行。

D又是非常愚蠢的错误,就不谈了。

码速应该继续加强,毕竟E差不多差好多打完了。

最后@DimensionTripper写了一篇优秀的神级算法学习笔记:莫比乌斯反演学习笔记和另外一篇神级学习笔记狄利克雷卷积学习笔记

Orz数学神仙