首页 > 其他分享 >231002校内赛

231002校内赛

时间：2023-10-05 16:46:08浏览次数：43  
标签：dep 校内 int ll read define 231002 inc

T1数独

pPXuCkT.jpg

题解

十分简单的一道模拟题

有sb少打了一个换行挂50分

#include<bits/stdc++.h>
#define N 15
using namespace std;
struct node{
	int a[N][N],be;
}t[N*10];
int T,n = 9,q;
int ferror(int cnt,int x,int y,int k){
	for(int i = 1;i<=n;i++)
		if(t[cnt].a[x][i]==k)
			return 1;
	for(int i = 1;i<=n;i++)
		if(t[cnt].a[i][y]==k)
			return 2;
	if(x%3==0) x--;
	if(y%3==0) y--;
	x/=3;y/=3;x*=3,y*=3;
	for(int i = 1;i<=3;i++)
		for(int j = 1;j<=3;j++){
			if(t[cnt].a[x+i][y+j]==k)
				return 3;
		}
	return 0;
}
int main(){
	freopen("sudoku.in","r",stdin);
	freopen("sudoku.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	string s;
	for(int i = 1;i<=19;i++){
		cin>>s;
		if(i%2==1) continue;
		else{
			for(int j = 0;j<=18;j++)
				if(j%2==1)
					t[0].a[(i+1)/2][(j+1)/2] = s[j]-'0';
		}
	}
	cin>>q;
	for(int cnt = 1;cnt<=q;cnt++){
		string s;
		int x,y,k;
		cin>>s;
		for(int i = 1;i<=n;i++)
			for(int j = 1;j<=n;j++)
				t[cnt].a[i][j] = t[cnt-1].a[i][j];
		switch(s[0]){
			case 'I':{
				cin>>x>>y>>k;
				if(t[cnt].a[x][y]){
					cout<<"Error!\n";
					continue;
				}
				int fl = ferror(cnt,x,y,k);
				if(fl==1) cout<<"Error:row!\n";
				else if(fl==2) cout<<"Error:column!\n";
				else if(fl==3) cout<<"Error:square!\n";
				else{
					cout<<"OK!\n";
					t[cnt].a[x][y] = k;
				}
				break;
			}
			case 'D':{
				cin>>x>>y;
				if(t[cnt].a[x][y]){
					cout<<"OK!\n";
					t[cnt].a[x][y] = 0;
				}else cout<<"Error!\n";
				break;
			}
			case 'Q':{
				cin>>x>>y;
				if(t[cnt].a[x][y])
					cout<<"Error!\n";
				else{
					vector<int>g;
					for(int k = 1;k<=n;k++)
						if(ferror(cnt,x,y,k)==0)
							g.push_back(k);
					cout<<g.size()<<"\n";
					for(int i : g) cout<<i<<"\n";
				}
				break;
			}
			case 'M':{
				for(int i = 1;i<=n;i++)
					for(int j = 1;j<=n;j++)
						t[cnt].a[i][j] = 0;
				cin>>x>>y;
				int tot1 = 0,tot2 = 0;
				for(int i = 1;i<=n;i++){
					for(int j = 1;j<=n;j++){
						if(ferror(cnt,i,j,t[x].a[i][j])==0)
							tot1++,t[cnt].a[i][j] = t[x].a[i][j];
						else if(ferror(cnt,i,j,t[y].a[i][j])==0)
							tot2++,t[cnt].a[i][j] = t[y].a[i][j];
					}
				}
				cout<<tot1<<" "<<tot2<<"\n";
				break;
			}
			case 'P':{
				for(int i = 1;i<=19;i++){
					if(i%2==1){
						cout<<"+-+-+-+-+-+-+-+-+-+\n";
						continue;
					}
					for(int j = 1;j<=19;j++){
						if(j%2==1) cout<<"|";
						else cout<<t[cnt].a[(i+1)/2][(j+1)/2];
					}
					cout<<"\n";
				}
				break;
			}
		}
	}
	return 0;
}

T2 回家

pPXuihF.jpg

题解

需要各位先了解一下折线法

对于这个过程我们不妨反过来看，将家设为原点，要在 \(k\) 步内走到距离为 \(n\) 的位置

设正着走了 \(x\) 步，那么向后走了 \(x-n\) 步，且每一步结束之后坐标都 \(>0\)

那么根据折线法很容易得出 \(\binom{2x-n}{x}\)，但还是有几种情况需要排除出去

对于在只剩下 \(z\) 的时间却距离大于 \(z\) 的情况需要排除

只需要减去 \(2\) 倍的\(\binom{2x-n-1}{x}\)

为什么是 \(2\) 倍？

因为通过折线法作图之后会发现限制就是一条线段，越过这条线段的都不行

而上面的式子只能算到一部分，将所有算到的按照线段再对称一次那么就正好算到所有遗漏的

#include<bits/stdc++.h>
#define mod 998244353
#define N 5000010 
#define ll long long
using namespace std;
int n,k,fac[N<<1],inv[N<<1];
int ksm(int x,int y){
	int res = 1;
	while(y){
		if(y&1) res = (ll)res*x%mod;
		x = (ll)x*x%mod;
		y>>=1;
	}
	return res;
}
int C(int a,int b){
	if(b>a) return 0;
	return (ll)fac[a]*inv[b]%mod*inv[a-b]%mod;
}
signed main(){
	freopen("home.in","r",stdin);
	freopen("home.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>k;
	if(n>k){
		cout<<"0";
		return 0;
	}
	fac[0] = 1;
	for(int i = 1;i<=n+k;i++)
		fac[i] = (ll)fac[i-1]*i%mod;
	inv[n+k] = ksm(fac[n+k],mod-2);
	for(int i = n+k-1;i>=0;i--)
		inv[i] = (ll)inv[i+1]*(i+1)%mod;
	ll ans = 0;
	for(int i = n;i<=k;i+=2){
		ll tmp = ((ll)C(i,(i+n)/2)-2ll*C(i-1,(i+n)/2)%mod+mod)%mod;
		ans = (ans+(ll)tmp*ksm(inv[2],i)%mod)%mod;
	}
	cout<<ans;
	return 0;
}

T3 王国

pPXu19e.jpg

题解

显然这道题可以分为两个部分

第一步，对于每一支军队，确定其能获得最大的利益

第二步，确定军队在约束条件下获得的最大利益和

我们先考虑第一步

显然可以使用弗洛伊德算法求出任意两点间的距离

由于城堡可以被攻破多次，显然对于处于同一地点的城堡，如果其收益小于等于其他城堡且防御力大于等于该城堡，则其一定不会被选中

如此我们便可以使得一个地点的所有城堡按照防御力和收益同时递减的方式排列

同样地，我们令一个地点的军队按照攻击力递减排列

不难发现，对于处于同一地点的军队，他们所匹配的城堡一定是单调的

所以对于处于同一地点的军队，我们最多访问所有军队 \(1\) 次

对于每个军队，我们最多访问每个地点一次

所以总时间复杂度为 \(\mathcal O(ns)\)

对于第二步

我们先把答案设置为所有收益为正的军队的收益和

我们把所有含有依赖关系的军队分为两组，第一组的所有军队收益为正

第二组的所有军队收益为负

对于第一组另原点向其链接容量为收益的边

对于第二组另原点向其链接容量为收益相反数的边

对于所有依赖关系，依赖军队向其被依赖军队链接容量无穷的边

减去当前图的最小割即为最终答案

#include<bits/stdc++.h>
#define re register
#define inc(i,j,k) for(re int i=j;i<=k;i++)
#define dec(i,j,k) for(re int i=j;i>=k;i--)
#define ll long long
#define int long long
using namespace std;
const int MAXN=105;
const int MAXM=200005;
const ll inf=100000000000000;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9'){x=x*10+ch-'0',ch=getchar();}
	return f*x;
}
int n,m,s,b,dis[MAXN][MAXN],a,c,x,f,p,val,d,g,ru[MAXM],cnt=1,head[MAXM],t,S,T,dep[MAXM],tmp;
ll ans,dp[MAXM];
inline void floyd(){
	inc(k,1,n){
		inc(i,1,n){
			inc(j,1,n) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
		}
	}
}
struct spaceship{
	int a,f,p,val,num;
	bool flag;
	spaceship(int aa,int ff,int pp,int vval,bool fflag,int nnum){a=aa,f=ff,p=pp,val=vval,flag=fflag,num=nnum;}
};
struct castal{
	int d,g;
	castal(int dd,int gg){d=dd,g=gg;}
};
vector<spaceship> ship[MAXN];
vector<castal> cas[MAXN],cass[MAXN];	
bool cmp1(spaceship x,spaceship y){return x.a<y.a;}
bool cmp2(castal x,castal y){return x.d<y.d;}
struct egde{
	int to,nxt;
	ll flow;
}e[MAXM<<2];
bool use[MAXM];
inline void add(int a,int b,ll c){
	e[++cnt].to=b;
	e[cnt].nxt=head[a];
	head[a]=cnt;
	e[cnt].flow=c;
}
bool bfs(){
	queue<int> q;
	inc(i,0,s+1) dep[i]=-1; 
	q.push(S),dep[S]=1;
	while(q.size()){
		int u=q.front();
		q.pop();
		for(re int i=head[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(dep[v]==-1&&e[i].flow){
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	}
	return dep[T]!=-1;
}
ll dfs(int u,ll f){
	if(u==T) return f;
	ll res=f,k=0;
	for(re int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(dep[u]+1==dep[v]&&e[i].flow){
			k=dfs(v,min(f,e[i].flow));
			if(!k) dep[v]=-1;
			e[i].flow-=k;
			e[i^1].flow+=k;
			res-=k;
		}
	}
	return f-res;
}
signed main(){
	
	freopen("kingdom.in","r",stdin);
	freopen("kingdom.out","w",stdout);
	n=read(),m=read();
	inc(i,1,n){
		inc(j,1,n) dis[i][j]=1000;
	}
	inc(i,1,m){
		a=read(),c=read();
		dis[c][a]=dis[a][c]=1;
	}
	inc(i,1,n) dis[i][i]=0;
	floyd();
	s=read(),b=read(),t=read();
	S=0,T=s+1;
	inc(i,1,s){
		x=read(),a=read(),f=read(),p=read();
		ship[x].push_back(spaceship(a,f,p,0,0,i));
	}
	inc(i,1,b){
		x=read(),d=read(),g=read();
		cas[x].push_back(castal(d,g));
	}
	inc(i,1,n) sort(ship[i].begin(),ship[i].end(),cmp1);
	inc(i,1,n) sort(cas[i].begin(),cas[i].end(),cmp2);
	inc(i,1,n){
		for(re int j=0;j<cas[i].size();j++){
			while(j<cas[i].size()&&cass[i].size()&&cas[i][j].g<cass[i][cass[i].size()-1].g) j++;
			if(j>=cas[i].size()) break;
			cass[i].push_back(cas[i][j]);
		}
	}
	inc(i,1,n){
		inc(j,1,n){
			if(!cass[j].size()) continue;
			int l=-1;
			for(re int k=0;k<ship[i].size();k++){
				while(l+1<cass[j].size()&&cass[j][l+1].d<=ship[i][k].a) l++;
				if(l!=-1&&ship[i][k].f>=dis[i][j]) ship[i][k].flag=1,ship[i][k].val=max(ship[i][k].val,cass[j][l].g);
			}
		}
	}
	inc(i,1,n){
		for(re int j=0;j<ship[i].size();j++){
			use[ship[i][j].num]=ship[i][j].flag;
			if(use[ship[i][j].num]) dp[ship[i][j].num]=ship[i][j].val-ship[i][j].p;
			else dp[ship[i][j].num]=-inf;
			ans+=max((ll)0,dp[ship[i][j].num]);
		}
	}
	inc(i,1,t){
		a=read(),c=read();
		add(a,c,inf),add(c,a,0);
	}
	inc(i,1,s){
		if(dp[i]>0) add(S,i,dp[i]),add(i,S,0);
		else if(dp[i]<0) add(i,T,-dp[i]),add(T,i,0);
	}
	while(bfs()) while(tmp=dfs(S,inf)) ans-=tmp;
	printf("%lld",ans);
}

T4

照常，没改，略过

标签：dep,校内,int,ll,read,define,231002,inc
From： https://www.cnblogs.com/cztq/p/17743507.html

相关文章

  • 230930校内赛
    T1洛阳怀题解首先非常容易求出的是所有的\(\gcd\)对于\(\gcd\)而言，如果它的分数是负数，那么将它除去一定会使这个数列得分变大所以只用求出所有的\(\gcd\)的分数并判断正负以及是否除过当前答案了就可以了还有一点是因为\(\gcd\)是单调不降的，所以可以从后往前查保证......
  • 20231002
    23/10/02NOIP模拟赛总结时间安排1:50-2:40先看了T1和T2，直接过样例。2:40-3:00T3没想到正解，先把40%打了。3:00-3:50上了个厕所，发现T3正解直接枚举，写完和自己的暴力对拍。3:50-4:00看了看后3题，感觉都不好做。4:00-4:50感觉T4是DP，但不会设状态，去打T5,T6暴力。4:50-5:40......
  • 【231002CHEM-1】方解石和石英得经过盐酸的洗礼才能鉴别
    我常去的钻石湾海滩边有一圈防波堤，防波堤内测有大片大大小小的石头，石头之间有时能捡到一些半透明的石头，样子有点像冰糖晶体。我起初一直以为这些石头是小块石英，因为硬度透明度形状都相似。某日我捡了一大块方解石晶体，之所以没被认成石英是因为它块大偏黄，和地质书中图片很像。当时挺......
  • 2023年中国高校计算机大赛-团队程序设计天梯赛（GPLT）上海理工大学校内选拔赛（同步赛)
    A.AXorBProblem（计数）输入511223输出9说明点击查看代码#include<bits/stdc++.h>#defineIOSios::sync_with_stdio(false);cin.tie(0),cout.tie(0)#defineintlonglongusingnamespacestd;constintN=2e5+10;unordered_map<int,int>......
  • 230925校内赛
    T1开挂我卢本伟没有开挂题解挺简单的，不过我写的比较麻烦因为我们需要让多的尽可能多来让少的尽可能少，所以会想到用栈来存储需要更改的数，靠近栈底就需要更多次数来更改，栈顶则更少最后只用记录下来所有的次数并按从多到少依次分配从小到大的修改代价#include<bits/stdc++.h......
  • 230927校内赛
    T1集合题解很明显的一道树形\(dp\)题我也没看出来dalao们说有一道\(ddp\)的题转移方式一模一样于是都切了，就我是sb首先有一个非常明显的性质在于所有的被选的点一定是可以构成一颗连通子树的最终选取的\(k\)个点一定是从这颗子树中最远点对的一个点沿着这颗子树直......
  • 校内互测第一周(East!XI~East!XV)总结(窝还是退役吧QAQ
    ==真是不想说啥了。。。像我这种沙茶蒟蒻还是早点滚粗的好。。。Day1East!XI出题人：18357打开题瞬间傻了。。。三道树上问题。。。三道。。。T1：给定一棵N个节点的无根树，求每个节点到其它的节点的∑(路径长度xorM)。M<=15TM这傻逼题我写了个0~15的Trie树。。。明明记录个0~15的数......
  • 230729校内赛
    回文一句话题意：从左上角到右下角的路径上的字母能组成回文串的路径有几条题解暴力做法是从左上角和右下角分别往对方\(dp\)，复杂度为\(\mathcalO(n^4)\)因为状态只有在\(x1+x2+y1+y2=n+m+2\)时合法，则确定三个变量即可推出剩下一个变量，复杂度为\(\mathcalO(n^3)\)......
  • 校内模拟赛赛后总结
    前记（开始写于\(2023.9.9\)）（本来是不想写的，但是看到学长以及身边人都写，思考了一下，感觉有点用，于是也写了）（里面也写了一些闲话）（以前的比赛我就记个排名得了，懒得补了）7.20~7.22CSP模拟1~3没考7.24CSP模拟4(rk6)7.25CSP模拟5(rk3)7.26CSP模拟6(rk23)7.27......
  • 230722校内赛
    T1CF576D题解我们根据边的出现时间分成\(m\)段对于每一段，设\(f_{T,i}\)表示\(T\)时刻，\(i\)节点能否走到，那么走一步就是个矩阵乘法对于某一段，我们从终点开始bfs可以就可以求出答案，矩阵乘法用bitset优化复杂度\(\mathcal{O}(m^2+\frac{ω}{mn^3}logT)\)#includ......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99