526互联

The 2021 Sichuan Provincial Collegiate Programming Contest

发布时间 2023-12-02 16:18:06作者: 空気力学の詩

Preface

下下周还要去打重庆市赛，最近就找些省赛来练练手

不得不说省赛的签到题是真的多，人均10+的过题看起来还是很恐怖的

这场虽然因为徐神缺席，而且前面的题目都让祁神来写导致罚时略高，但无所谓反正最后也摸到了11题（主要是没有字符串）

A. Chuanpai

某不知题意的签到

#include<bits/stdc++.h>

int ans[13]={0, 0, 1, 1, 2, 2, 3, 3, 3, 2, 2, 1, 1};
int main(){
	int t; scanf("%d", &t);
	while (t--){
		int n; scanf("%d", &n);
		if (n<=12) printf("%d\n", ans[n]);
		else printf("0\n");	
	}
	return 0;	
}

B. Hotpot

注意到经过\(2n\)轮后锅一定是空的，因此可以先模拟一遍\(2n\)轮的情况，再模拟剩下的情况

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+5;
int t, n, k, m, A[N], ans[N];
bool vis[N];
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> t;
	while (t--){
		cin >> n >> k >> m;
		for (int i=0; i<n; ++i) cin >> A[i];
		for (int i=0; i<n; ++i) ans[i]=0;
		for (int i=1; i<=k; ++i) vis[i]=false;
		
		for (int i=0; i<2*n; ++i){
			if (!vis[A[i%n]]) vis[A[i%n]]=true;
			else vis[A[i%n]]=false, ++ans[i%n];
		}
		for (int i=0; i<n; ++i) ans[i]*=(m/(2*n));
		for (int i=0; i<m%(2*n); ++i){
			if (!vis[A[i%n]]) vis[A[i%n]]=true;
			else vis[A[i%n]]=false, ++ans[i%n];
		}
		for (int i=0; i<n; ++i) cout << ans[i] << (i==n-1 ? '\n' : ' ');
	}
	return 0;	
}

C. Triangle Pendant

刚体力学，启动

祁神比赛时候推出了三根绳子都绷直的情况，结果后面发现还有一根/两根绳子绷直的情况，直接寄

D. Rock Paper Scissors

不难发现后手的策略一定是，当知道了先手出的牌后，优先出能赢的牌，若没有就出打平的牌，否则只能输了

而先手的策略一定是选择出某种牌之后直接把这种牌出完，因此可以全排列枚举先手的策略然后模拟算一遍即可

#include<bits/stdc++.h>
using namespace std;
#define int long long

signed main(){
	int t; scanf("%lld", &t);
	while (t--){
		int b[3], d[3], tmp1[3], tmp2[3];
		for (int i=0; i<3; ++i) scanf("%lld", &b[i]);
		for (int i=0; i<3; ++i) scanf("%lld", &d[i]);
		int ans=1e18;
		for (int i=0; i<3; ++i) for (int j=0; j<3; ++j) for (int k=0; k<3; ++k){
			if (i==j || i==k || j==k) continue;
			int tans=0;
			memcpy(tmp1, b, sizeof(b));
			memcpy(tmp2, d, sizeof(d));
			
			int cur=(i+1)%3;

			while (tmp1[i]>0){
				int res=min(tmp1[i], tmp2[cur]);
				tmp1[i]-=res; tmp2[cur]-=res;
				if (cur==(i+1)%3) tans+=res;
				if (cur==(i-1+3)%3) tans-=res;
				--cur; if (cur<0) cur+=3;
			}
//			printf("i=%d tans=%d\n", i, tans);
			
			cur=(j+1)%3;
			while (tmp1[j]>0){
				int res=min(tmp1[j], tmp2[cur]);
				tmp1[j]-=res; tmp2[cur]-=res;
				if (cur==(j+1)%3) tans+=res;
				if (cur==(j-1+3)%3) tans-=res;
				--cur; if (cur<0) cur+=3;
			}
//				printf("j=%d tans=%d\n", j, tans);
			
		 	cur=(k+1)%3;
		 	while (tmp1[k]>0){			 
				int res=min(tmp1[k], tmp2[cur]);
				tmp1[k]-=res; tmp2[cur]-=res;
				if (cur==(k+1)%3) tans+=res;
				if (cur==(k-1+3)%3) tans-=res;
				--cur; if (cur<0) cur+=3;
			}
//				printf("k=%d tans=%d\n", k, tans);
			
			ans = min(ans, tans);
		}
		printf("%lld\n", ans);
	}
	return 0;	
}

E. Don’t Really Like How The Story Ends

寄了一个小时才发现没判重边，我还以为做法假了

不难发现可以贪心构造，考虑已经处理了前\(i\)个点，现在要尝试把\(i+1\)加进来

按照DFS序找到最靠近栈顶，且还有未访问邻居的点\(x\)，若\(x\)和\(i+1\)有边则直接加入\(i+1\)，否则必须新加入一条\(x\)和\(i+1\)的边

不难发现用这种方法构造出的答案一定是最小的

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+5;
int t, n, m;
set<int> st[N];
int stk[N], top=-1;
int deg[N];

signed main(){
	//freopen("1.in", "r", stdin);
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> t;
	while (t--){
		cin >> n >> m;
		for (int i=1; i<=n; ++i) st[i].clear();
		memset(deg, 0, (n+1)*sizeof(int));
		for (int i=1; i<=m; ++i){
			int u, v; cin >> u >> v;
			if (u==v) continue;
			if (st[u].count(v)) continue;
			st[u].insert(v); st[v].insert(u);
			++deg[u]; ++deg[v];
		}
		
		int ans=0;
		top=-1; stk[++top]=1;
		for (int i=2; i<=n; ++i){
			while (top>0 && deg[stk[top]]<=0) --top;
			if (0==st[stk[top]].count(i)){
				++ans;
//				printf("u=%d v=%d\n", stk[top], i);
			}
			for (int v : st[i]){
				if (v<i) --deg[v], --deg[i];	
			}
			stk[++top]=i;
		}
		cout << ans << '\n';
	}
	return 0;	
}

F. Direction Setting

一眼网络流傻逼题

考虑把边看成左边的一排点，原图中的点看作右边的一排点

对于左边的点，从源点向其连容量为\(1\)的边；而右边的点向汇点连容量为\(a_i\)的边

对于每条边的两个端点\(x_i,y_i\)，将其向右边对应的点各连容量为\(1\)的边即可

最后的答案就是\(m\)减去最大流，方案也很好求

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define RI register int
#define CI const int&
using namespace std;
const int N=305;
int T,n,m,x[N],y[N];
namespace Network_Flow
{
	const int NN=1005,MM=1e6+5,INF=1e9;
	struct edge
	{
		int to,nxt,v;
	}e[MM<<1]; int cnt=1,head[NN],cur[NN],dep[NN],s,t; queue <int> q;
	inline void clear(void)
	{
		for (RI i=1;i<=t;++i) head[i]=0; cnt=1;
	}
    inline void addedge(CI x,CI y,CI z)
    {
        e[++cnt]=(edge){y,head[x],z}; head[x]=cnt;
        e[++cnt]=(edge){x,head[y],0}; head[y]=cnt;
    }
    #define to e[i].to
    inline bool BFS(void)
    {
        memset(dep,0,t+1<<2); dep[s]=1; q=queue <int>(); q.push(s);
        while (!q.empty())
        {
            int now=q.front(); q.pop();
			for (RI i=head[now];i;i=e[i].nxt)
            if (e[i].v&&!dep[to]) dep[to]=dep[now]+1,q.push(to);
        }
        return dep[t];
    }
    inline int DFS(CI now,CI tar,int dis)
    {
        if (now==tar) return dis; int ret=0;
        for (RI& i=cur[now];i&&dis;i=e[i].nxt)
        if (e[i].v&&dep[to]==dep[now]+1)
        {
            int dist=DFS(to,tar,min(dis,e[i].v));
            if (!dist) dep[to]=INF;
            dis-=dist; ret+=dist; e[i].v-=dist; e[i^1].v+=dist;
            if (!dis) return ret;
        }
        if (!ret) dep[now]=0; return ret;
    }
    #undef to
    inline int Dinic(int ret=0)
    {
        while (BFS()) memcpy(cur,head,t+1<<2),ret+=DFS(s,t,INF); return ret;
    }
    inline void solve(void)
    {
    	for (RI i=1,j;i<=m;++i)
		{
			bool flag=0; for (j=head[i];j;j=e[j].nxt)
			if (e[j].to!=s&&!e[j].v) putchar(e[j].to-m==x[i]?'1':'0'),flag=1;
			if (!flag) putchar('0');
		}
		putchar('\n');
    }
};
using namespace Network_Flow;
int main()
{
	//freopen("F.in","r",stdin); freopen("F.out","w",stdout);
	for (scanf("%d",&T);T;--T)
	{
		RI i; int a; for (scanf("%d%d",&n,&m),s=n+m+1,t=s+1,i=1;i<=n;++i) scanf("%d",&a),addedge(m+i,t,a);
		for (i=1;i<=m;++i) scanf("%d%d",&x[i],&y[i]),addedge(s,i,1),addedge(i,m+x[i],1),addedge(i,m+y[i],1);
		printf("%d\n",m-Dinic()); solve(); clear();
	}
	return 0;
}

G. Hourly Coding Problem

说实话没太看懂题解在讲什么，到vjudge上找了各代码一看300行直接不想补了

H. Nihongo wa Muzukashii Desu

签到题，但是有人自作聪明忘了行く的特殊变形我不说是谁（样例没过也能交是真高手）

#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
int n;
int main()
{
	//freopen("H.in","r",stdin); freopen("H.out","w",stdout);
	ios::sync_with_stdio(0); cin.tie(0);
	for (cin>>n;n;--n)
	{
		string s; cin>>s; if (s=="ikimasu")
		{
			cout<<"itte"<<endl; continue;
		}
		reverse(s.begin(),s.end());
		if (s.size()>=7&&s[5]=='h'&&s[6]=='s')
		{
			string t=s.substr(7); reverse(t.begin(),t.end());
			t+="shite"; cout<<t<<endl;
		} else
		if (s.size()>=6&&s[5]=='g')
		{
			string t=s.substr(6); reverse(t.begin(),t.end());
			t+="ide"; cout<<t<<endl;
		} else
		if (s.size()>=6&&s[5]=='k')
		{
			string t=s.substr(6); reverse(t.begin(),t.end());
			t+="ite"; cout<<t<<endl;
		} else
		if (s.size()>=6&&s[5]=='m'||s[5]=='b'||s[5]=='n')
		{
			string t=s.substr(6); reverse(t.begin(),t.end());
			t+="nde"; cout<<t<<endl;
		} else
		if (s.size()>=7&&s[5]=='h'&&s[6]=='c')
		{
			string t=s.substr(7); reverse(t.begin(),t.end());
			t+="tte"; cout<<t<<endl;
		} else
		if (s.size()>=6&&s[5]=='r')
		{
			string t=s.substr(6); reverse(t.begin(),t.end());
			t+="tte"; cout<<t<<endl;
		}
	}
	return 0;
}

I. Monster Hunter

挺有意思的一个题，猜了猜结论也艹过去了

首先一眼想到二分答案，这样check的话就只用考虑用已知数量的\(1,2,3\)来干掉所有怪兽了

考虑如果只有\(1,2\)的话就是各很典的贪心，先尽量用\(2\)，如果所有数都被干到\(1\)后还有剩下的\(2\)就接着干，然后再用剩下的\(1\)

而加入\(3\)后我们考虑先把\(3\)用完，然后套上面的贪心，经过一些手玩我们可以发现：

  • 当某个怪物的血量为大于等于\(3\)的奇数时，可以用一个\(3\)去干它
  • 当某个怪物的血量为大于等于\(6\)的偶数时，可以用两个\(3\)去干它

但要注意我们要尽量多的留下偶数，因为这样可以尽量优化\(2\)的使用，因此要优先处理第一种情况再考虑第二种情况

然后如果还有多余的\(3\)，直接优先干剩余的较大的数即可，然后再套上面的贪心即可

总复杂度\(O(n\log (m\times a_i))\)

#include<cstdio>
#include<iostream>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,a[N],m,h[N],c[5];
inline bool check(CI lim)
{
	RI i; static int tc[5],th[N];
	for (i=1;i<=3;++i) tc[i]=c[i]*(lim/n);
	for (i=1;i<=lim%n;++i) ++tc[a[i]];
	for (i=1;i<=m;++i) th[i]=h[i];
	for (i=1;i<=m&&tc[3]>0;++i)
	if (th[i]>=3&&th[i]%2==1) --tc[3],th[i]-=3;
	for (i=1;i<=m&&tc[3]>0;++i)
	if (th[i]>=6&&th[i]%2==0)
	{
		int dlt=min(tc[3]/2,th[i]/6);
		tc[3]-=dlt*2; th[i]-=dlt*6;
	}
	if (tc[3]==1)
	{
		int pos=0; for (i=1;i<=m;++i) if (th[i]>th[pos]) pos=i;
		--tc[3]; th[pos]-=3;
	}
	for (i=1;i<=m&&tc[3]>0;++i) if (th[i]==4) --tc[3],th[i]-=3;
	for (i=1;i<=m&&tc[3]>0;++i) if (th[i]==2) --tc[3],th[i]=0;
	for (i=1;i<=m&&tc[3]>0;++i) if (th[i]==1) --tc[3],th[i]=0;
	for (i=1;i<=m&&tc[2]>0;++i) if (th[i]>0)
	{
		int dlt=min(tc[2],th[i]/2);
		tc[2]-=dlt; th[i]-=dlt*2;
	}
	for (i=1;i<=m&&tc[2]>0;++i) if (th[i]==1) --tc[2],th[i]=0;
	for (i=1;i<=m&&tc[1]>0;++i)
	{
		int dlt=min(tc[1],th[i]);
		tc[1]-=dlt; th[i]-=dlt;
	}
	for (i=1;i<=m;++i) if (th[i]>0) return 0;
	return 1;
}
signed main()
{
	//freopen("I.in","r",stdin); freopen("I.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i; for (i=1;i<=3;++i) c[i]=0;
		for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld",&a[i]),++c[a[i]];
		for (scanf("%lld",&m),i=1;i<=m;++i) scanf("%lld",&h[i]);
		int l=1,r=1e14,mid,ret=0; while (l<=r)
		if (check(mid=l+r>>1)) ret=mid,r=mid-1; else l=mid+1;
		printf("%lld\n",ret);
	}
	return 0;
}

J. Ants

我对这题题意一知半解，但据说就是个模拟题，不过实现细节比较考验人需要仔细思考一下

用two pointers或队列实现的话可能比较简单

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1e6+5;
const int LEN = 1e9+1;
int A[N], d[N];
struct Node{
	int id, pos;
	bool operator<(const Node &b){return pos<b.pos;}		
};
vector<Node> vL, vR;
bool vis[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int n, L, R; cin >> n >> L >> R;
	for (int i=1; i<=n; ++i) cin >> A[i];
	for (int i=1; i<=n; ++i) cin >> d[i];
	for (int i=1; i<=n; ++i){
		if (0==d[i]){
			vL.push_back(Node{i, A[i]}), vR.push_back(Node{i, LEN+A[i]});
			vL.push_back(Node{i, 2*LEN+A[i]}), vR.push_back(Node{i, 2*LEN+LEN+A[i]});
		}else{
			vL.push_back(Node{i, 2*LEN-A[i]}), vR.push_back(Node{i, LEN-A[i]});
			vL.push_back(Node{i, 2*LEN+2*LEN-A[i]}), vR.push_back(Node{i, 2*LEN+LEN-A[i]});
		}
	}
	sort(vL.begin(), vL.end()); sort(vR.begin(), vR.end());
	
	int mn=min(L, R);
	int ans=0;
	if (mn>=n) ans+=2*LEN*(mn/n), L-=mn/n*n, R-=mn/n*n;
	
	int pL=0, pR=0;
	int mx=0;
	while (pL<vL.size() && pR<vR.size()){
		if (vL[pL].pos<=vR[pR].pos){
			if (!vis[vL[pL].id]){
				if (L>0) --L;
				else mx=max(mx, vL[pL].pos), vis[vL[pL].id]=true;
			}
			++pL;
		}else{
			if (!vis[vR[pR].id]){
				if (R>0) --R;
				else mx=max(mx, vR[pR].pos), vis[vR[pR].id]=true;
			}
			++pR;
		}
	}
	
	while (pL<vL.size()){
		if (!vis[vL[pL].id]){
			if (L>0) --L;
			else mx=max(mx, vL[pL].pos), vis[vL[pL].id]=true;
		}
		++pL;
	}
	while (pR<vR.size()){
		if (!vis[vR[pR].id]){
			if (R>0) --R;
			else mx=max(mx, vR[pR].pos), vis[vR[pR].id]=true;
		}
		++pR;
	}
	
	cout << ans+mx << '\n';
	return 0;	
}

K. K-skip Permutation

签到题，把\(\bmod k\)相同的数升序排在一起即可

#include<bits/stdc++.h>
using namespace std;

signed main(){
	int n, k; scanf("%d%d", &n, &k);
	vector<int> vec;
	for (int i=1; i<=k; ++i){
		for (int j=0; j*k+i<=n; ++j) vec.push_back(j*k+i);	
	}
	for (int i=0; i<n; ++i){
		if (i>0) putchar(' ');
		printf("%d", vec[i]);	
	}
	return 0;	
}

L. Spicy Restaurant

乍一看很吓人，其实仔细看数据范围会发现点权很小

因此可以做\(100\)遍BFS，每次加入点权等于当前值的所有点，做一个多源BFS来更新到每个点的答案即可

#include<bits/stdc++.h>
using namespace std;

const int N = 5e5+5;
const int INF = 0x3f3f3f3f;
int n, m, q;
struct Qry{
	int p, ans;
}qry[N];
vector<int> vec[105], ask[105];
vector<int> edg[N];
int dis[N];
int que[N], fr=0, ed=-1;

signed main(){	
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> q;
	for (int i=1; i<=n; ++i){
		int w; cin>>w;
		vec[w].push_back(i);	
	}
	for (int i=1; i<=m; ++i){
		int u, v; cin >> u >> v;
		edg[u].push_back(v); edg[v].push_back(u);	
	}
	
	for (int i=1; i<=q; ++i){
		int p, a; cin >> p >> a;
		qry[i].p=p;
		ask[a].push_back(i);
	}
	
	memset(dis, 0x3f, (n+1)*sizeof(int));
	for (int w=1; w<=100; ++w){
		fr=0, ed=-1;
		for (int x : vec[w]) que[++ed]=x, dis[x]=0;
		while (fr<=ed){
			int u=que[fr++];
			for (int v : edg[u]){
				if (dis[v]>dis[u]+1){
					dis[v]=dis[u]+1;
					que[++ed]=v;
				}
			}
		}
		
		for (int id : ask[w]){
			qry[id].ans = (dis[qry[id].p]<INF ? dis[qry[id].p] : -1);
		}
	}
	for (int i=1; i<=q; ++i) printf("%d\n", qry[i].ans);
	
	return 0;	
}

M. True Story

题意初看不明所以，其实仔细一想会发现如果一个人已经选择出发了，那么他一定能坐上飞机

因此就是找一个最大的\(p_i-t_i\)，每个人最多能用的时间就是这个，直接判断即可

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1e5+5;
int p[N], t[N], s[N];
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int n, k, x; cin >> n >> k >> x >> p[0];
	for (int i=1; i<=n; ++i) cin >> s[i];
	for (int i=1; i<=k; ++i) cin >> t[i];
	for (int i=1; i<=k; ++i) cin >> p[i];
	int ret=0;
	for (int i=0; i<=k; ++i){
		ret=max(ret, p[i]-t[i]);
	}
	int cnt=0;
	for (int i=1; i<=n; ++i){
		if (ret*s[i]>=x) ++cnt;
	}
	cout << cnt << '\n';
	return 0;	
}

Postscript

这场博客写的巨快，因为没啥难的题

不知道是省赛都是这个难度还是这场特别简单，久违地写了两位数的题