博客

广州大学第十七届ACM大学生程序设计竞赛（同步赛）

  • Post author:
  • Post category:其他



A-萤火虫

思路：

  1. 我们只用操作1，是不是能贪心都前面n-k个数都是0。
  2. 如果我们对于1<=i<=n，归为k个集合，即s[j]=s[i%k],我们每操作一次操作1，s[0]~s[k-1]都会一起加1或者减1，如果我们最后能减到都同时0，就说明成功了。
  3. 而我们可以贪心到最后只剩k个数，那么他们就对应各自的s[j]，我们可以对最后这k个数操作一次操作1，尽可能多的使这一次将更多数变为0，剩下不为0的显然只能使用操作2，即答案。 
#include <bits/stdc++.h>
using namespace std;
#define ll     long long
const int N = 2e5 + 10;

ll a[N];
int main()
{
	int t;
	cin>>t;
	while (t--)
		{
			int n,k,x;
			cin>>n>>k;
			fill(a,a+n+1,0);
			for (int i=0; i<n; ++i)
				{
					cin>>x;
					a[i%k]+=x;//把数分为k个集合，每次操作1就等效对每个集合操作
				}
			if (k==1)
				{
					cout<<0<<endl;
					continue;
				}
			sort(a,a+k);
			int len=0;
			int p=1;
			for (int i=1; i<k; ++i)
				{
					if (a[i]==a[i-1])p++;
					else
						{
							len=max(p,len),p=1;//最后一次操作1尽可能使多的集合变为0
						}
				}
			len=max(p,len);
			cout<<k-len<<endl;
		}
	return 0;
}


B-罗伯特

思路：

显然用bfs去跑即可 ，为了使一个点不要重复经过，我们可以记录每个点在方向f时的最短路是多少，只更新更短的 

#include <bits/stdc++.h>
using namespace std;
#define ll     long long
#define int ll
typedef pair<int, int> pii;
const int N = 110;

struct node
{
	int d,x,y,p,f;
	bool operator<(const node&k)const
	{
		return d>k.d;
	}
};
int dp[N][N][60][5];
bool vis[N][N][60][5];
int ways[5][3]= {{-1,0},{1,0},{0,-1},{0,1}};
pii mp[N][N];
char ch[N][N];
int32_t main()
{
	int n,m,p,k;
	cin>>n>>m>>k>>p;
	int x1,y1,x2,y2;
	for (int i=1; i<=k; ++i)
		{
			cin>>x1>>y1>>x2>>y2;
			mp[x1][y1]= {x2,y2};
			mp[x2][y2]= {x1,y1};
		}
	memset(dp,0x3f,sizeof(dp));
	for (int i=1; i<=n; ++i)for (int j=1; j<=m; ++j)
			{
				cin>>ch[i][j];
				if (ch[i][j]=='U')ch[i][j]='0';
				else if (ch[i][j]=='D')ch[i][j]='1';
				else if (ch[i][j]=='L')ch[i][j]='2';
				else if (ch[i][j]=='R')ch[i][j]='3';
			}
	priority_queue<node>q;
	dp[1][1][0][3]=0;
	q.push({0,1,1,0,3});
	while (!q.empty())
		{
			node u=q.top();
			q.pop();
			if (vis[u.x][u.y][u.p][u.f])continue;
			vis[u.x][u.y][u.p][u.f]=1;
			if (u.x==n&&u.y==m)
				{
					cout<<"YES"<<endl;
					cout<<dp[u.x][u.y][u.p][u.f]<<endl;
					return 0;
				}
			if (ch[u.x][u.y]=='.')
				{
					for (int i=0; i<4; ++i)
						{
							node v=u;
							v.x+=ways[i][0],v.y+=ways[i][1],v.p+=(i!=v.f);
							v.f=i;
							if (1<=v.x&&v.x<=n&&1<=v.y&&v.y<=m&&ch[v.x][v.y]!='#')
								{
									if (mp[v.x][v.y].first!=0)
										{
											pii tmp=mp[v.x][v.y];
											v.x=tmp.first,v.y=tmp.second;
										}
									if (v.p<=p&&dp[v.x][v.y][v.p][v.f]>dp[u.x][u.y][u.p][u.f]+1)
										{
											dp[v.x][v.y][v.p][v.f]=v.d=dp[u.x][u.y][u.p][u.f]+1;
											q.push(v);
										}
								}
						}
				}
			else if (('0'<=ch[u.x][u.y]&&ch[u.x][u.y]<='3')||ch[u.x][u.y]=='@')
				{
					node v=u;
					if (ch[u.x][u.y]!='@')v.f=ch[u.x][u.y]-'0';
					v.x+=ways[v.f][0],v.y+=ways[v.f][1];
					if (1<=v.x&&v.x<=n&&1<=v.y&&v.y<=m&&ch[v.x][v.y]!='#')
						{
							if (mp[v.x][v.y].first!=0)
								{
									pii tmp=mp[v.x][v.y];
									v.x=tmp.first,v.y=tmp.second;
								}
							if (v.p<=p&&dp[v.x][v.y][v.p][v.f]>dp[u.x][u.y][u.p][u.f]+1)
								{
									dp[v.x][v.y][v.p][v.f]=v.d=dp[u.x][u.y][u.p][u.f]+1;
									q.push(v);
								}
						}
				}
		}
	cout<<"NO"<<endl;
	return 0;
}


C-论AE自动化的重要性

思路：

裸拓扑，反向建边即可 

#include <bits/stdc++.h>
using namespace std;
#define ll     long long
#define int ll
const int N = 2e5 + 10;
const int mod=1e9+7;

ll a[N],in[N];
struct node
{
	int next,to,w;
} edge[N<<1];
int head[N],num;

void add(int u,int v,ll w)
{
	edge[++num].next=head[u];
	edge[num].to=v,edge[num].w=w;
	head[u]=num;
}

int32_t main()
{
	int n,m,k;
	cin>>n>>m>>k;
	int x,y,c;
	for (int i=1; i<=k; ++i)
		{
			cin>>x>>y;
			a[x]+=y;
		}
	for (int i=1; i<=m; ++i)cin>>x>>y>>c,add(y,x,c),in[x]++;
	queue<int>q;
	ll ans=0;
	for (int i=1; i<=n; ++i)if (!in[i])q.push(i);
	while (!q.empty())
		{
			int u=q.front();
			q.pop();
			ans=(ans+a[u])%mod;
			for (int i=head[u]; i; i=edge[i].next)
				{
					int v=edge[i].to,w=edge[i].w;
					a[v]=(a[v]+a[u]*w)%mod;
					if (--in[v]==0)q.push(v);
				}
		}
	cout<<ans<<endl;
	return 0;
}


G-Clannad

思路：

  1. 目标是取n+1个不相同的数，使得这些数存在有两个数差是n倍数。因为n+1>n，所以如果这n个数mod n。必然有两个余数相同，那么他们的差绝对值就是n了
  2. 所以问题转化为如果x>=n+1(使得可以取n+1个不同的数），那就是组合数，在x个数选n+1个数。所以预处理组合数即可 
#include <bits/stdc++.h>
using namespace std;
#define ll     long long
#define endl             "\n"
const int N = 5e3 + 10;
const int mod=1e9+7;

ll c[N][N];
void init()
{
	c[0][0]=1;
	for (int i=1; i<=5e3; ++i)
		{
			c[i][0]=1;
			for (int j=1; j<=i; ++j)c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
		}
}

int main()
{
	std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t,n,x;
	cin>>t;
	init();
	while (t--)
		{
			cin>>n>>x;
			if (n+1>x)
				{
					cout<<-1<<endl;
					continue;
				}
			else
				{
					cout<<c[x][n+1]<<endl;
				}
		}
	return 0;
}


H-性格差劲的久美子

思路：

  1. 首先 如果a的数字b里面没有，显然这个数字排在哪里都可以。
  2. 而对应x,y同时属于a与b数组，那么我们假设x在b中出现范围是L[x]~R[x],y范围是L[y]~R[y]，那么我们需要满足x,y在a的子串出现范围是R[y]<=L[x]
  3. 所以我们可以先处理b中每个数在b的出现范围
  4. 然后顺序遍历a。设t[i]表示在i位置之后出现了多少个位置

    1. 如果
      a[i]\nsubseteq b
      ,那么显然答案子串可以直接无视顺序加它。
    2. 如果属于，那么a[i]可以匹配b中所有在a[i]最后一次出现后的数字+1（t记录的数字都是在a数组中在a[i]出现前的，我们这样加（表示他们都是在b中顺序是在a之后出现的）。然后再对a[i]第一次出现及其之前的位置更新t[i],表示这些区间可以出现a[i]
  5. 因为维护区间数个数，每次都是单点修改，所以树状数组功能足够了 
#include <bits/stdc++.h>
using namespace std;
#define ll     long long
#define endl             "\n"
typedef pair<int, int> pii;
const int N = 2e5 + 10;
int t[N],a[N],b[N];
unordered_map<int,pii>mp;
void add(int x,int w)
{
	for (int i=x; i; i-=i&-i)t[i]=max(t[i],w);
}
int ask(int x)
{
	int ans=0;
	for (int i=x; i<=N; i+=i&-i)ans=max(ans,t[i]);
	return ans;
}

int main()
{
	int n,m;
	cin>>n;
	for (int i=1; i<=n; ++i)cin>>a[i];
	cin>>m;
	for (int i=1; i<=m; ++i)
		{
			cin>>b[i];
			if (!mp[b[i]].first)mp[b[i]]= {i,i};//更新每个在b中出现的数的出现区间
			else mp[b[i]].second=i;
		}
	int ans=0,sum=0;
	for (int i=1; i<=n; ++i)
		{
			if (!mp[a[i]].first)sum++;//b中没出现直接加
			else
				{
					int tmp=ask(mp[a[i]].second)+1;//找符合条件的最长子串，寻找在b数组顺序在a[i]之后出现的数（这些数在a数组中是在a之前出现，先出现才能被加到t数组里面）
					ans=max(ans,tmp);
					add(mp[a[i]].first,tmp);//更新t数组中出现的数字的区间
				}
		}
	cout<<ans+sum<<endl;
	return 0;
}


K-因子模仿

思路：

注意到[l,r]胜利与否结果就是r是1还是0，所以 我们在区间操作中维护每个数被修改次数即可，奇数次转变奇偶性，偶数次等价没修改。所以其实是树状数组裸题 

#include <bits/stdc++.h>
using namespace std;
#define ll     long long
#define endl             "\n"
const int N = 1e6 + 10;
int t[N];
int n,q,x,op,l,r;
void add(int x,int w)
{
	for (int i=x; i<=n; i+=i&-i)t[i]+=w;
}
int ask(int x)
{
	int ans=0;
	for (int i=x; i; i-=i&-i)ans+=t[i];
	return ans;
}
int main()
{
	std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>q>>x>>x>>x>>x;
	char c;
	for (int i=1; i<=n; ++i)
		{
			cin>>c;
			if (c=='1')add(i,1),add(i+1,-1);
		}
	while (q--)
		{
			cin>>op>>l>>r;
			if (op==1)
				{
					add(l,1),add(r+1,-1);//区间修改
				}
			else
				{
					if (ask(r)&1)//单点查询
						{
							cout<<"Magical Splash Flare"<<endl;
						}
					else
						{
							cout<<"HoloPsychon"<<endl;
						}
				}
		}
	return 0;
}


版权声明：本文为WQhuanm原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。