手残比赛系列 +3 +3 +3 +3 +3……

话不多说进入正题

A. Diagonal Walking

瞎dp一波即可 贪心也对(当时没仔细想直接开始敲dp)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<cstdlib>
#include<queue>
#include<vector>
#define ll long long
using namespace std;

int n;
int dp[1010][2]={0};
char chs[1010]={0};

inline void readx(int& x)
{
	x=0; int k=1; register char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

int main()
{
	readx(n);
	scanf("%s",chs);
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=dp[0][1]=0;
	for (int i=1;i<=n;i++)
	{
		dp[i][0]=min(dp[i-1][0],dp[i-1][1])+1;
		if (chs[i-1]=='U' && chs[i-2]=='R')
		{
			dp[i][1]=min(dp[i-2][0],min(dp[i-2][1],dp[i-1][0]))+1;
		}
		else if (chs[i-1]=='R' && chs[i-2]=='U')
		{
			dp[i][1]=min(dp[i-2][0],min(dp[i-2][1],dp[i-1][0]))+1;
		}
	}
	
	printf("%d\n",min(dp[n][0],dp[n][1]));
	return 0;
}

B. String Typing

枚举终点然后判断能不能复制即可。

记得倒序,要不会被aaaaaaaaa这种卡掉

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<cstdlib>
#include<queue>
#include<vector>
#define ll long long
using namespace std;

int n;
char chs[1010]={0};

inline void readx(int& x)
{
	x=0; int k=1; register char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

inline bool judgex(int spos)
{
	for (int i=0;i<spos;i++)
		if (chs[i]!=chs[spos+i]) return false;
	return true;
}

int main()
{
	readx(n); scanf("%s",chs);
	
	for (int i=n-1;i;i--) if (i%2)
	{
		if (judgex((i+1)/2))
		{
			printf("%d\n",n-i+(i+1)/2);
			return 0;
		}
	}
	printf("%d\n",n);
	return 0;
}

C. Matrix Walk

尝试能不能通过上下的移动确定一行的宽度y

然后fixed宽度,把不合法的上下移动,左右移动判掉即可

特判不动的情况和没有上下移动的情况

x轴直接设置10^9

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<cstdlib>
#include<queue>
#include<vector>
#define ll long long
using namespace std;

int n;
int seq[200010]={0};
int sizx=-1,sizy=-1,cachex;
bool fixedx=false;

inline void readx(int& x)
{
	x=0; int k=1; register char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

int main()
{
	readx(n);
	for (int i=1;i<=n;i++) readx(seq[i]);
	
	for (int i=2;i<=n;i++)
	{
		if (seq[i]>seq[i-1]+1 || seq[i]<seq[i-1]-1)
		{
			fixedx=true;
			cachex=abs(seq[i]-seq[i-1]);
			if (cachex!=sizx && sizx!=-1)
			{
				printf("NO\n");
				return 0;
			}
			else if (sizx==-1) sizx=cachex;
		}
	}
	
	for (int i=1;i<n;i++) if (seq[i]==seq[i+1]) { printf("NO\n"); return 0; }
	
	if (!fixedx)
	{
		printf("YES\n");
		printf("1 1000000000\n");
		return 0;
	}
	else
	{
		for (int i=2;i<=n;i++) 
		{
			if (seq[i]<=seq[i-1]+1 && seq[i]>=seq[i-1]-1)
				if ((seq[i]-1)/sizx!=(seq[i-1]-1)/sizx)
				{
					printf("NO\n");
					return 0;
				}
		}
		printf("YES\n");
		printf("1000000000 %d\n",sizx);
	}
	return 0;
}

D. Fight Against Traffic

两遍SPFA然后枚举左右端点判定距离即可

注意有两种情况,还有就是ans要除2

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<cstdlib>
#include<queue>
#include<vector>
#define ll long long
using namespace std;

struct edge { int pre,to; } edge[2010]={0};

int nodenum,edgenum,at=0,pointer[1010]={0},fx,tx,stx,tox,stdis;
bool conn[1010][1010]={0};

queue<int> que;
bool vis[1010]={0};
int dis[1010][2]={0};

inline void readx(int& x)
{
	x=0; int k=1; register char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

inline void Insert()
{
	at++;
	edge[at].pre=pointer[fx];
	edge[at].to=tx;
	pointer[fx]=at;
	at++;
	edge[at].pre=pointer[tx];
	edge[at].to=fx;
	pointer[tx]=at;
}

inline void SPFA(int starx,int wx)
{
	int cache1,prex;
	vis[starx]=true; que.push(starx); dis[starx][wx]=0;
	while (!que.empty())
	{
		cache1=que.front(); que.pop();
		prex=pointer[cache1];
		while (prex)
		{
			if (dis[edge[prex].to][wx]>dis[cache1][wx]+1)
			{
				dis[edge[prex].to][wx]=dis[cache1][wx]+1;
				if (!vis[edge[prex].to])
				{
					vis[edge[prex].to]=1;
					que.push(edge[prex].to);
				}
			}
			prex=edge[prex].pre;
		}
	}
	memset(vis,0,sizeof(vis));
}

int main()
{
	readx(nodenum); readx(edgenum); readx(stx); readx(tox);
	for (int i=1;i<=edgenum;i++)
	{
		readx(fx); readx(tx);
		Insert();
		conn[fx][tx]=conn[tx][fx]=1;
	}
	
	memset(dis,0x3f,sizeof(dis));
	SPFA(stx,0); SPFA(tox,1);
	
	int dis1,dis2,dis3,dis4,ans=0;
	for (int i=1;i<=nodenum;i++)
	{
		for (int j=1;j<=nodenum;j++) if (i!=j && (!conn[i][j]))
		{
			dis1=dis[i][0]; dis2=dis[j][1];
			dis3=dis[i][1]; dis4=dis[j][0];
			if (dis1+dis2+1>=dis[tox][0] && dis3+dis4+1>=dis[tox][0]) 
			{
				ans++;
			}
		}
	}
	printf("%d\n",ans/2);
	return 0;
}

E. Water Taps

把式子移一下就会发现是贪心

还没写出来,写出来再说

F. Runner’s Problem

时间不够了,没看题目

G. Castle Defense

先差分一遍把初始的\rm defense指数算出来

然后二分最小值,用贪心的方法判定

区间影响那就差分一下,假设判定的时候当前不足,还要让i+1加上补充的数目,i+2 \times \rm Range -1减去数目,然后从左到右扫就行

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<cstdlib>
#include<queue>
#include<vector>
#define ll long long
using namespace std;

ll resx,n,rangex;
ll seq[500110]={0};
ll seq2[500110]={0};

inline ll minLL(ll a,ll b) { if (a<b) return a; return b; }
inline ll maxLL(ll a,ll b) { if (a>b) return a; return b; }

inline void readx(ll& x)
{
	x=0; ll k=1; register char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

inline bool judgex(ll botm)
{
	memset(seq2,0,sizeof(seq2));
	ll hasx=resx;
	for (int i=1;i<=n;i++)
	{
		seq2[i]+=seq2[i-1];
		if (seq[i]+seq2[i]<botm)
		{
			ll restx=botm-seq[i]-seq2[i];
			if (restx>hasx) return false;
			else
			{
				hasx-=restx;
				seq2[i+1]+=restx;
				seq2[minLL(n+1,i+2*rangex+1)]-=restx;
			}
		}
	}
	return true;
}


int main()
{
	readx(n); readx(rangex); readx(resx);
	for (int i=1;i<=n;i++) readx(seq[i]);
	
	for (int i=1;i<=n;i++)
	{
		seq2[maxLL(i-rangex,1)]+=seq[i];
		seq2[minLL(n+1,i+rangex+1)]-=seq[i];
	}
	memset(seq,0,sizeof(seq));
	for (int i=1;i<=n;i++) seq[i]=seq[i-1]+seq2[i];
	
	ll lx=0,rx=2e18,mid,ans=0;
	while (lx<=rx)
	{
		mid=(lx+rx)>>1;
		if (judgex(mid)) 
		{
			lx=mid+1;
			ans=mid;
		}
		else rx=mid-1;
	}
	
	printf("%lld\n",ans);
	return 0;
}

H. Path Counting

留坑

I. Yet Another String Matching Problem

留坑


发表评论

电子邮件地址不会被公开。 必填项已用*标注