2018-2019 Russia Open High School Programming Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred)

前言

有一场下午的cf，很滋磁啊，然后又和dalao(见右面链接)组队打了，dalao直接带飞我啊。

这是一篇题解，也是一篇总结，当然，让我把所有的题目都写个题解是不可能的了。

按照开题顺序讲吧。

在开始前有现场赛的成绩，所以可以看出来哪道是傻逼题，当然还是滋磁啊。

M - The Pleasant Walk

我被分到了这道题，当然是因为我太弱了啊，dalao当然是要去做神仙题了。

好像没什么可说的了，直接扫不就行了。。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

//const int Maxn=;

int main() {

//	freopen("test.in","r",stdin);

	int n,k;

	scanf("%d%d",&n,&k);

	int las=1,ans=1,x,last;

	scanf("%d",&last);

	for(int i=2;i<=n;i++) {

		scanf("%d",&x);

		ans=max(ans,i-las);

		if(x==last) las=i;

		last=x;

	}

	ans=max(ans,n+1-las);

	printf("%d",ans);

	return 0;

}

A - Company Merging

%%%zhy

#include<map>

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int maxn=2e5+100;

int siz[maxn],n,m,top[maxn],maxx;

ll ans;

int main(){

//	freopen("1.in","r",stdin);

	scanf("%d",&n);

	for(int i=1;i<=n;i++){

		scanf("%d",&m);

		int maxt=0,a;

		for(int i=1;i<=m;i++)

			scanf("%d",&a),maxt=max(maxt,a);

		top[i]=maxt,siz[i]=m;

		maxx=max(maxx,maxt);

	}

	for(int i=1;i<=n;i++)

		ans+=1ll*(maxx-top[i])*siz[i];

	printf("%I64d\n",ans);

	return 0;

}

然后就卡了题。我滚去看D，dalao去看L，然而发现D是个构造，似乎是转化成图然后搞搞？好像找到两个点之间没有边然后强制令这两个点编号为1,2，然后从这两个点广搜，依次标号为3到n，这就是互不重复的。然后把2改成1就有重复的了。

然后 Wrong answer on test 2 ?我连样例都没过？我明明过了啊。。再交一次还是WA？然后就只能用肉眼调试了。。好像没错啊。。woc，我没输出YES！加上了再交，A了。。

瞬间有种自杀的冲动。。

D - Similar Arrays

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int Maxn=210000;

int to[Maxn],nxt[Maxn],first[Maxn],vis[Maxn],n,m,u,v,sxz,zhy,d[Maxn],tot=1,cnt;

inline void add(int u,int v) {

	to[tot]=v;

	nxt[tot]=first[u];

	first[u]=tot++;

	to[tot]=u;

	nxt[tot]=first[v];

	first[v]=tot++;

}

int main() {

//	freopen("test.in","r",stdin);

	scanf("%d%d",&n,&m);

	for(int i=1;i<=m;i++) {

		scanf("%d%d",&u,&v);

		add(u,v);

		d[u]++;

		d[v]++;

	}

	int flag=0;

	for(int i=1;i<=n;i++)

		if(d[i]<n-1) {

			flag=1;vis[sxz=i]=1;

			for(int j=first[i];j;j=nxt[j]) vis[to[j]]=1;

			for(int j=1;j<=n;j++)

				if(!vis[j]) {zhy=j;break;}

			break;

		}

	if(flag==0) {

		puts("NO");

		return 0;

	}

	queue<int>q;

	memset(vis,0,sizeof(vis));

	vis[sxz]=1;vis[zhy]=2;

	q.push(sxz),q.push(zhy);

	cnt=3;

	while(!q.empty()) {

		int now=q.front();q.pop();

		for(int i=first[now];i;i=nxt[i])

			if(!vis[to[i]]) {

				vis[to[i]]=cnt++;

				q.push(to[i]);

			}

	}

	for(int i=1;i<=n;i++)

		if(vis[i]==0) {

			vis[i]=cnt++;

			q.push(i);

			while(!q.empty()) {

				int now=q.front();q.pop();

				for(int i=first[now];i;i=nxt[i])

					if(!vis[to[i]]) {

						vis[to[i]]=cnt++;

						q.push(to[i]);

					}

			}

		}

	puts("YES");

	printf("%d",vis[1]);

	for(int i=2;i<=n;i++) printf(" %d",vis[i]);

	putchar('\n');

	vis[zhy]=1;

	printf("%d",vis[1]);

	for(int i=2;i<=n;i++) printf(" %d",vis[i]);

	putchar('\n');

	return 0;

}

然后dalao给我讲了L的题意，他还说他看不懂样例？太fake了吧。我来看看，这不是能一眼秒掉啊，直接二分不就好了。。

L - Berland University

#include<map>

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

ll n,m,x,y,a,b,k;

bool check(ll t){

	ll p=min(t,a);

	ll siz=p*x;

	p=min(t,b);

	siz+=p*y;

	return siz>=t*k;

}

int main(){

//	freopen("1.in","r",stdin);

	scanf("%I64d%I64d%I64d%I64d%I64d",&n,&m,&a,&b,&k);

	if(m%2) x=m/2+1,y=m/2;

	else x=y=m/2;

	if(a>b) swap(a,b),swap(x,y);

	ll l=0,r=n+1,mid,ans;

	while(l<r){

		mid=l+r>>1;

		if(check(mid))

			ans=mid,l=mid+1;

		else

			r=mid;

	}

	printf("%I64d\n",ans);

	return 0;

}

然后dalao说B很不可做啊。。我看看，这不是直接模拟吗？秒掉秒掉。。

B - LaTeX Expert

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#include<vector>

using namespace std;

const int Maxn=210000;

char s[Maxn],a[100][Maxn];

vector<char> c[100];

int b[Maxn],cnt;

void readf() {

	while(getchar()!='\\');

}

int len;

void readw() {

	len=0;

	char ch=getchar();memset(s,0,sizeof(s));

	while(!isalpha(ch)) ch=getchar();

	while(isalpha(ch)) s[len++]=ch,ch=getchar();

}

void readl() {

	len=0;

	char ch=getchar();memset(s,0,sizeof(s));

	while(ch!='\\') s[len++]=ch,ch=getchar();

}

int main() {

//	freopen("test.in","r",stdin);

	while(1) {

		readf();readw();

		if(strcmp(s,"begin")==0) break;

		readw();

		cnt++;

		strcpy(a[cnt],s);

	}readf();readw();

	for(int i=1;i<=cnt;i++) {

		readw();

		for(int j=1;j<=cnt;j++)

			if(strcmp(s,a[j])==0)

				b[j]=i;

		readl();

		for(int j=0;j<len;j++) c[i].push_back(s[j]);

		readw();

	}

	int flag=0;

	for(int i=1;i<=cnt;i++) if(b[i]!=i) flag=1;

	if(flag) {

		puts("Incorrect");

		puts("\\begin{thebibliography}{99}");

		for(int i=1;i<=cnt;i++) {

			printf("\\bibitem{%s}",a[i]);

			for(int j=0;j<c[b[i]].size();j++)

				printf("%c",c[b[i]][j]);

		}

		puts("\\end{thebibliography}");

	}

	else puts("Correct");

	return 0;

}

然后dalao说I题是水题？(orz)我看看。。好的真是水题，读入好麻烦啊，那就让dalao先看看读入怎么读(%%%)，我这种蒟蒻就只能打打杂了。好了，过了样例了，WA了？写个拍看看。。拍了几处错之后怎么还没A？都拍了两千组了好吧。。在用肉眼调调吧。这个读入怎么可能错呢...woc，我读入错了。。改上就A了。。我怎么又有种想要自杀的冲动？

I - Minimal Product

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#include<vector>

using namespace std;

typedef long long ll;

const int Maxn=21000000;

int t;

ll n,l,r,x,y,z,b[Maxn],a[Maxn];

int main() {

//	freopen("test.in","r",stdin);

	scanf("%d",&t);

	while(t--) {

		scanf("%I64d%I64d%I64d%I64d%I64d%I64d%I64d%I64d",&n,&l,&r,&x,&y,&z,&b[1],&b[2]);

		for(int i=3;i<=n;i++) b[i]=b[i-2]*x+b[i-1]*y+z;

		for(int i=1;i<=n;i++) b[i]&=0xffffffff;

		for(int i=1;i<=n;i++) a[i]=b[i]%(r-l+1)+l;

//scanf("%I64d",&n);

//for(int i=1;i<=n;i++)

//scanf("%I64d",&a[i]);

		ll zhy=a[1],ans=0x7fffffffffffffff;

		for(int i=2;i<=n;i++)

			if(zhy<a[i]) ans=min(ans,a[i]*zhy);

			else zhy=a[i];

		while(a[n]>=0&&n) n--;

		zhy=a[n];

		for(int i=n-1;i>0;i--)

			if(a[i]<0) {

				if(zhy>a[i]) ans=min(ans,a[i]*zhy);

				else zhy=a[i];

			}

		if(ans==0x7fffffffffffffff) puts("IMPOSSIBLE");

		else printf("%I64d\n",ans);

	}

	return 0;

}

听说dalao看到了一个字符串？我再看看有什么可做的吧。

这里有个象棋？马的遍历？普及-？好吧，是让他们归位，并且步数不超过1300？写个爆搜先。。

好像。。一只马从这个点走到另一个点最多7步？那不就随便水水就好了？于是就让dalao做这道题(orz)，我再去看看还有什么可做的。

好像C做的也很多，再看一眼。这不是傻逼题吗，怎么没有人做？于是就随便写了写，然而WA了，只过了样例？

好吧，这个好像是有毛病的，改好了，TLE？被卡常了吗？500000很有可能卡set啊，那就换成unordered_set。

还是T？再从网上抄个输入输出优化，还T？

dalao已经A了。%%%%%%%%

E - Horseback Riding

#include<map>

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

struct node{

	int x,y;

}zhy;

struct nod{

	int a,b,c,d;

};

nod ac[2000];

queue<node>q;

int f[10][10][10][10],num;

int u[8]={1,2,-1,-2,-1,2,1,-2};

int v[8]={2,1,-2,-1,2,-1,-2,1};

int ok[10][10],ans;

void bfs(int x,int y){

	f[x][y][x][y]=1;

	zhy.x=x,zhy.y=y;

	q.push(zhy);

	while(!q.empty()){

		zhy=q.front(),q.pop();

		int ux=zhy.x,uy=zhy.y;

		for(int i=0;i<8;i++){

			int vx=ux+u[i],vy=uy+v[i];

			if(vx>0&&vx<9&&vy>0&&vy<9&&!f[x][y][vx][vy]){

				f[x][y][vx][vy]=f[x][y][ux][uy]+1;

				zhy.x=vx,zhy.y=vy;

				ans=max(ans,f[x][y][vx][vy]);

				q.push(zhy);

			}

		}

	}

}

char s[10];

void mov(int a,int b,int c,int d){

	if(a==c&&b==d) return;

	for(int i=0;i<8;i++){

		int vx=a+u[i],vy=b+v[i];

		if(vx>0&&vx<9&&vy>0&&vy<9&&f[a][b][c][d]-1==f[vx][vy][c][d]){

			if(ok[vx][vy]){

				mov(vx,vy,c,d);

				num++;

				ac[num].a=a,ac[num].b=b,ac[num].c=vx,ac[num].d=vy;

			}

			else{

				num++;

				ac[num].a=a,ac[num].b=b,ac[num].c=vx,ac[num].d=vy;

				mov(vx,vy,c,d);

			}

			break;

		}

	}

}

int main(){

//	freopen("1.in","r",stdin);

//	freopen("1.out","w",stdout);

	for(int i=1;i<=8;i++)

		for(int j=1;j<=8;j++)

			bfs(i,j);

	int n;

	scanf("%d",&n);

	int nx=1,ny=1;

	for(int i=1;i<=n;i++){

		scanf("%s",s);

		int x=s[0]-'a'+1,y=s[1]-'0';

		ok[x][y]=1;

	}

	while(ok[nx][ny]){

		nx++;

		if(nx==9) nx=1,ny++;

		if(ny>8){

			printf("0\n");

			return 0;

		}

	}

	int err=0;

	for(int y=1;y<=8;y++){

		for(int x=1;x<=8;x++)

			if(ok[x][y]&&(y>ny||(y==ny&&x>nx))){

				mov(x,y,nx,ny);

				ok[x][y]=0,ok[nx][ny]=1;

				while(ok[nx][ny]){

					nx++;

					if(nx==9) nx=1,ny++;

					if(ny>8){

						err=1;

						break;

					}

				}

				if(err==1) break;

			}

		if(err==1) break;

	}

	printf("%d\n",num);

	for(int i=1;i<=num;i++)

		printf("%c%c-%c%c\n",ac[i].a+'a'-1,ac[i].b+'0',ac[i].c+'a'-1,ac[i].d+'0');

	return 0;

}

然而我还没过啊。。dalao没事干也来帮我看，我就向他讲我的复杂度为什么是对的。。等等，我写的好像是n方啊。。好像再开个set就好了。改上WA了，连样例都没过？然后改了许多地方，还是WA？完了啊，还有十分钟了。。

哎，我好像看出来哪里错了，改上，woc，cf打不开了啊。。gg。dalao就去试试vpn，结果试了半天，还是不行，完了，这次真凉了。再看看，woc，能打开了。。

最后终于在结束前4分钟A了。。竟然还有罚时比我们少的？

C - New Year Presents

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#include<vector>

#include<unordered_set>

#include<assert.h>

#include<set>

using namespace std;

const int Maxn=110000;

int tt,n,x,tot[Maxn],zhy[Maxn],s[Maxn],t[Maxn],top,num,sum,bs,m,a[Maxn];

vector<int> vi[Maxn];

unordered_set<int> se[Maxn];

set<int> b;

set<int>::iterator nh[Maxn];

const int InputBufferSize = 67108864;//输入缓冲区大小

const int OutputBufferSize = 67108864;//输出缓冲区大小

namespace input

{

    char buffer[InputBufferSize],*ss,*eof;

    inline void init()

    {

        assert(stdin!=NULL);

        ss=buffer;

        eof=ss+fread(buffer,1,InputBufferSize,stdin);

    }

    inline bool read(int &x)

    {

        x=0;

        int flag=1;

        while(!isdigit(*ss))ss++;

        if(eof<=ss)return false;

        if(*ss=='-')flag=-1,ss++;

        while(isdigit(*ss))x=x*10+*ss++-'0';

        x*=flag;

        return true;

    }

}

namespace output

{

    char buffer[OutputBufferSize];

    char *ss=buffer;

    inline void flush()

    {

        assert(stdout!=NULL);

        fwrite(buffer,1,ss-buffer,stdout);

        ss=buffer;

        fflush(stdout);

    }

    inline void print(const char ch)

    {

        if(ss-buffer>OutputBufferSize-2)flush();

        *ss++=ch;

    }

    inline void print(int x)

    {

        char buf[25]= {0},*p=buf;

        if(x<0)print('-'),x=-x;

        if(x==0)print('0');

        while(x)*(++p)=x%10,x/=10;

        while(p!=buf)print(char(*(p--)+'0'));

    }

}

using namespace input;

using namespace output;

int main() {

//	freopen("test.in","r",stdin);

	init();

	read(tt),read(m);

	for(int i=1;i<=tt;i++) {

		read(n);

		for(int j=1;j<=n;j++) {

			read(x);

			vi[i].push_back(x);

		}

		sum+=n;

	}

	int mo=sum%tt;

	sum/=tt;

	for(int i=1;i<=tt;i++)

		if(vi[i].size()<=sum) {

			s[++top]=i;int len=vi[i].size();tot[top]=len;

			for(int j=0;j<len;j++) se[top].insert(vi[i][j]);

		}

		else t[++num]=i;

	for(int i=1;i<=num;bs+=vi[t[i]].size()-a[t[i]],i++)

		if(mo) a[t[i]]=sum+1,mo--;

		else a[t[i]]=sum;

	for(int i=1;i<=top;i++)

		if(mo) a[s[i]]=sum+1,mo--;

		else a[s[i]]=sum;

	for(int i=1;i<=top;i++) {

		int x=s[i];

		if(tot[i]!=a[x]) b.insert(i);

	}

	print(bs);print('\n');

	for(int i=1;i<=m;i++) zhy[i]=*b.begin(),nh[i]=b.begin();

	for(int i=1;i<=num;i++) {

		int len=vi[t[i]].size(),sxz=len-a[t[i]];

		for(vector<int>::iterator j=vi[t[i]].begin();j!=vi[t[i]].end()&&sxz;j++) {

			int x=*j;

			nh[x]=b.lower_bound(zhy[x]);

			if(nh[x]!=b.end()) zhy[x]=*nh[x];

			while(nh[x]!=b.end()&&se[zhy[x]].count(x)) {

				nh[x]++;if(nh[x]!=b.end()) zhy[x]=*nh[x];

			}

			if(nh[x]!=b.end()) {

				tot[zhy[x]]++;

				if(tot[zhy[x]]==a[s[zhy[x]]]) b.erase(nh[x]);

				se[zhy[x]].insert(x);

				sxz--;

				print(t[i]),print(' '),print(s[zhy[x]]),print(' '),print(x),print('\n');

			}

		}

	}

	flush();

	return 0;

}

于是就这么滚粗了。

orz zhy %%%%%%%%%%%%%%%%%%%%%%%%

K - Right Expansion Of The Mind

原来K这么简单啊。。先判断第一个串里面第一个在第二个串里没出现的字符的位置，如果第一个串从开始到这个字符与另一个相等，并且第二个串出现的字符集合相同的话就是互为子序列。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#include<vector>

#include<unordered_set>

#include<map>

#include<set>

using namespace std;

const int Maxn=1100000;

const int Maxm=110000;

int n,num,tot=100000,ch[Maxn][26],zhy,rot[Maxm],sum;

char a[Maxn],s[Maxn];

vector<int> vi[Maxm];

map<int,int> ma;

map<int,int> mb;

int main() {

//	freopen("test.in","r",stdin);

	scanf("%d",&n);

	for(int i=1;i<=n;i++) {

		scanf("%s%s",a,s);

		int lena=strlen(a),lens=strlen(s),st=0;

		for(int j=0;j<lens;j++) st|=(1<<(s[j]-'a'));

		if(!mb.count(st)) mb[st]=++sum,rot[sum]=sum;

		zhy=0;

		for(int j=lena-1;j>=0;j--)

			if((st&(1<<a[j]-'a'))==0) {

				zhy=j+1;

				break;

			}

		int now=rot[mb[st]],temp=0;

		while(temp!=zhy) {

			int x=a[temp]-'a';

			if(ch[now][x]==0) {

				tot++;ch[now][x]=tot;

			}

			now=ch[now][x];

			temp++;

		}

		if(!ma.count(now)) {

			num++;

			ma[now]=num;

		}

		vi[ma[now]].push_back(i);

	}

	printf("%d\n",num);

	for(int i=1;i<=num;i++) {

		int len=vi[i].size();

		printf("%d",len);

		for(auto j:vi[i]) printf(" %d",j);

		putchar('\n');

	}

	return 0;

}

巴特西