首页 > 其他分享 >新生赛10

新生赛10

时间：2024-10-04 14:33:06浏览次数：7  
标签：10 return int void 新生 else --

新生赛 10

今天没有学什么算法，主要是做了做往年的新生赛，虽然说估计应该最高只有一两个绿题的水平，基本上是黄题，但我的水平可以保证不能稳切绿题，黄题十有八九吃罚时。: (

A

贪心，一开始还煞有介事地开了个优先队列，给数组排了个序。

事实上优先队列等于没用，数组顺序不能更改，稳稳吃到 +2

#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>inline void re(T &x)
{
	x=0;
	int f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	x*=f;
}
template<typename T>inline void wr(T x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)wr(x/10);
	putchar(x%10^48);
}
int a[1000000];
int n;
signed main()
{
	re(n);
	for(int i=2;i<=n;++i)re(a[i]);
	int ans=0;
	for(register int i=2;i<=n;++i)
		ans+=a[i]*i;
	wr(ans);
	return 0;
}

B

模拟题。类似记忆化，还好 1Y 了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,x,y,d;
const int N=600;
char mp[N][N];
bool vis[N][N][4];
int cx[4]={-1,0,1,0},cy[4]={0,1,0,-1};
inline int getd(int nowd,int x,int y)
{
	if(mp[x][y]=='.')return nowd;
	else if(mp[x][y]=='/')
	{
		switch(nowd)
		{
			case 0:return 1;
			case 1:return 0;
			case 2:return 3;
			case 3:return 2;
		}
	}
	else // '\'
	{
		switch(nowd)
		{
			case 0:return 3;
			case 1:return 2;
			case 2:return 1;
			case 3:return 0;
		}
	}
}
inline int dfs(int x,int y,int d,int s)
{
	if(vis[x][y][d])return -1;
	if(x>n||x<1||y<1||y>m)return s;
	vis[x][y][d]=1;
	int tx=x+cx[d],ty=y+cy[d];
	return dfs(tx,ty,getd(d,tx,ty),s+1);
}
inline void solve()
{
	cin>>n>>m>>x>>y>>d;
	for(int i=1;i<=n;++i)
	{
		getchar();
		for(int j=1;j<=m;++j)
			mp[i][j]=getchar();
	}
	int ans=dfs(x,y,d,0);
	if(ans==-1)printf("Forever!");
	else cout<<ans;
}
signed main()
{
	solve();
	return 0;
}

C

人类智慧构造题，但好像还是挺好构造的，只不过我想了大概四十分钟才做出来，还是太废物了。

#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void re(T &x)
{
	x=0;
	int f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	x*=f;
}
template<typename T>inline void wr(T x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)wr(x/10);
	putchar(x%10^48);
}
int k;
int main()
{
	re(k);
	int p=0;
	for(int i=1;i<=k;++i)
	{
		printf("%d %d %d\n",p,p+1,p+21);
		if(i%2)p+=22;
		else p+=41;
	}
	return 0;
}

D

感觉是一道大概有绿题思维难度的博弈，自己仅仅独立做出来了 \(\frac{1}{4}\) ，后面看着题解自己思考了一些。

题意

有一个 01 串，长度为 \(n\) ，如果一个 \(1\) 的右边是 \(0\) 的话，可以向右移动这个 \(1\) ，当一个 \(1\) 在串的最末尾的时候，可以移动它并且得到一分。

现在有 \(A,B\) 两个玩家，问如果他们都 optimally 地进行操作， 问最后谁的得分更高。

分析

首先来说，对于最右边的 \(1\) ，如果它距离串的末尾的距离是偶数，那么当前的人去移动它就肯定是一个必胜态；反之就是一个必败态，当前的人一定不会去移动它（除非没有其他的 \(1\) 可以移动）。

1.根据以上理论我们不难知道当一个串末尾为 \(0\) ，且有 \(2\) 个 \(1\) 的时候，一定会出现平局（无论谁先手），也可以推广偶数个 \(1\) 的情况。

2.当一个串末尾为 \(0\) 且有奇数个 \(1\) 的时候，考虑末尾的 \(1\) 出于必胜态还是必败态，如果是必胜态，那么当前的人一定会去移动它，将它变为必败态，这时候一定不会有人去移动它，而是去交替移动左边的 \(1\) ，直到达到 \(...111110\) 的情况为止，那么此时轮到谁先手操作需要由初始态到现在状态的操作数决定。容易思考出：此时先手的人必定会输。

3.当一个串末尾为 \(1\) 且有奇数个 \(1\) 的时候，先手必定赢，因为先手得分以后就是平局态。

4.当一个串末尾为 \(1\) 且有偶数个 \(1\) 的时候，先手先得一分，然后变成第二种情况。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>inline void re(T &x)
{
	x=0;
	int f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	x*=f;
}
template<typename T>inline void wr(T x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)wr(x/10);
	putchar(x%10^48);
}
int n;
signed main()
{
	re(n);
	char c[1000010];
	int cnt=0;
	for(int i=1;i<=n;++i)
	{
		c[i]=getchar();
		if(c[i]=='1')cnt++;
	}
	int pos=n-1;
	for(;pos>=1;--pos)if(c[pos]=='1')break;
	if(c[n]=='0')
	{
		if(cnt%2==0)printf("Draw");
		else// 
		{
			int s=0;
			for(int i=pos,idx=n;i;--i)if(c[i]=='1')s+=n-1-i-(n-idx),idx--;
			if(s%2)printf("Nigu");
			else printf("Frizea");
		}
	}
	else
	{
		if(cnt%2==1)printf("Nigu");
		else
		{
			int s=0;
			for(int i=pos,idx=n;i;--i)if(c[i]=='1')s+=n-1-i-(n-idx),idx--;
			if(s%2)printf("Draw");
			else printf("Nigu");
		}
	}
	return 0;
}

E

分析

这个是一眼不能贪心，所以就DP了。

图方便写了个记忆化，感觉复杂度应该挺小的，结果由于是第一次写浮点数的DP，咱判断记忆化的时候好像还不能直接用等于号，于是就 T 了两三发，索性写DP了，但是由于边界和层与层的嵌套关系没有搞得太清楚，调了很久，最后记忆化也改出来了，DP也写出来了。

细节

这个题的阶段是天数，非常明显了，然后应该从最后一天倒着枚举。

虽然看着是四层循环，但是实际上很小，可以通过。

Code

#include<bits/stdc++.h>
using namespace std;
int n;
double a[500][500],dp[500][500][10],sum[500][500];
inline void pre()
{
	cin>>n;
	int len=(int)pow(2,n);
	for(register int i=1;i<=len;++i)
		for(register int j=1;j<=len;++j)
			scanf("%lf",&a[i][j]);	
	for(register int i=1;i<=len;++i)
		for(register int j=1;j<=len;++j)
			sum[i][j]=sum[i-1][j]+sum[i][j-1]+a[i][j]-sum[i-1][j-1];
				
}
double calc(int i,int j,int x,int y)
{
	return sum[x][y]-sum[x][j-1]-sum[i-1][y]+sum[i-1][j-1];
}
inline double get(int x,int y,int k)
{
	if(k>n)return 0.0;
	if(dp[x][y][k]>0)
		return dp[x][y][k];
	//calc
	int l=(int)pow(2,n-k);
	double ans=0.0,div=pow(2,k);
	for(register int i=x;i<=x+l;++i)
		for(register int j=y;j<=y+l;++j)
			ans=max(ans,calc(i,j,i+l-1,j+l-1)/div+get(i,j,k+1)); 
	return dp[x][y][k]=ans;
}
inline void memorized_search()
{
	int len=(int)pow(2,n);
	for(register int i=1;i<=len;++i)
		for(register int j=1;j<=len;++j)
			for(register int k=1;k<=n;++k)
				dp[i][j][k]=-1.0;
	printf("%.1lf",sum[len][len]-get(1,1,1));
}
inline void DP()
{
	int len=(int)pow(2,n);
	for(register int k=n;k>=1;--k)
	{
		int l=(int)pow(2,n-k+1);
		for(register int i=1;i+l-1<=len;++i)
		{
			for(register int j=1;j+l-1<=len;++j)
			{
				for(register int u=i;u<=i+l/2;++u)
					for(register int v=j;v<=j+l/2;++v)
						dp[i][j][k]=max(dp[i][j][k],(dp[u][v][k+1]+calc(u,v,u+l/2-1,v+l/2-1))/2.0);
			}
		}
	}
	printf("%.1lf",sum[len][len]-dp[1][1][1]);
}
int main()
{
	pre();
	DP();
//	memorized_search(); 
	return 0;
}

F

人类智慧题，不多赘述，吃罚时就是了。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>inline void re(T &x)
{
	x=0;
	int f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	x*=f;
}
template<typename T>inline void wr(T x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)wr(x/10);
	putchar(x%10^48);
}
int T;
bool check(int a,int b,int c)
{
	int t=0; 
	if(a==0)t++;
	if(c==0)t++;
	if(b==0)t++;
	return t<=1;
}
signed main()
{
	re(T);
	while(T--)
	{
		int a,b,c;
		re(a),re(b),re(c);
		if(b==c)puts("Yes");
		else if(!check(a,b,c))puts("No");
		else
		{
			if(b>c)swap(b,c);
			if((c-b)%3!=0)puts("No");
			else puts("Yes");
		}
	
	}
	return 0;
}

G

模拟题 \(O(t\sqrt n)\) 可以通过

#include<bits/stdc++.h>
using namespace std;
inline void check(int x)
{
	int i;
	int ans=0;
	for(i=1;i*i<x;++i)
		if(x%i==0)ans+=2;
	if(i*i==x)ans++;
	if(x%ans==0)puts("YES");
	else puts("NO");
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		check(n);
	}
	return 0;
 }

H

模拟题

Code

#include<bits/stdc++.h>
using namespace std;
inline void solve(string s)
{
	cin>>s;
	int len=s.length();
	if(s[5]=='l')
	{
		for(register int i=9;i<=len-4;++i)putchar(s[i]);
		putchar('\n');
	}
	else
		for(register int i=7;i<=len-4;++i)putchar(s[i]);
}
int main()
{
	int L;
	cin>>L;
	L-=2;
	string s;
	cin>>s;
	while(L--)
		solve(s);
	cin>>s;
	return 0;
}

I

乍一眼看是个DP，结果发现好像不能重复，看了题解发现是个二分加贪心，写完了还是过不了，但倒是可以过样例，鸽了，不想改这题了。

Code

#include<bits/stdc++.h>
using namespace std;
char tmp[1000100],s[1000100]; 
int all_i,len;
inline void pre()
{
	cin>>s;
	len=strlen(s);
	for(register int i=0;i<len;++i)
		if(s[i]=='I')all_i++;
}
inline bool check(int x)
{
	int remain_I=0,remain_O=0,finished_I=0,find_I=0;
	for(register int i=len-1;i>=0;--i)
	{
		if(s[i]=='I')
		{
			if(find_I!=x)find_I++,remain_I++;
			else if(remain_O)remain_I--,remain_O--,finished_I++;
		}
		if(s[i]=='O'&&remain_I!=0)remain_O++;
		if(s[i]=='N'&&remain_O!=0)remain_I--,remain_O--,finished_I++;
	}
	return finished_I==x;
}
inline int bs(int l,int r)
{
	if(l==r)return l;
	int mid=(l+r+1)>>1;
	if(check(mid))return bs(mid,r);
	else return bs(l,mid-1);
} 
int main()
{
	pre();
	cout<<bs(0,len);
	return 0;	
}
//IOIOIOIONIOIOI

标签：10,return,int,void,新生,else,--
From： https://www.cnblogs.com/Hanggoash/p/18446593

相关文章

  • 洛谷P10336 [UESTCPC 2024] 2-聚类算法
    涉及知识点：博弈、贪心题意Alice和Bob在玩选点游戏，所有的点在一个\(k\)维空间中，他们轮流选走一个点放入自己的集合中，Alice先手。定义集合\(S\)的权值\(val(S)\)为集合中点两两之间的\(k\)维曼哈顿距离之和。Alice的得分为\(val(S_A)-val(S_B)\)，Bob的得分为\(val(......
  • 20241003
    公交车(bus)显然的题目,答案就是所有连通块的大小减一之和#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e7+5;intn,m,fa[N],sz[N],ans;intfind(intx){if(fa[x]==x){returnx;}returnfa[x]=find......
  • wsl重装Ubuntu遇到的一些问题( WslRegisterDistribution failed with error: 0x800410
        不知道什么原因，VSCode连接WSLUbuntu总是失败，遂决定重装Ubuntu。    但是卸载原来的Ubuntu后，安装新的Ubuntu报错:WslRegisterDistributionfailedwitherror:0x80041002Error:0x80041002(null),查了比较多的帖子，使用了以下方法最终解决：1.关闭"适用于l......
  • Debuggers 1012：Introductory GDB
    OpenSecurityTraining2LearningPaths:VulnerabilityHunting&Exploitationpython：https://www.learnpython.org/路径图：https://ost2.fyi/OST2_LP_Vulns_Exploits.pdfDebuggers1012：IntroductoryGDB（与python）-->Architecture1001:x86-64Assembly-->R......
  • 20241003校模拟
    A纪念一下本人在校模拟用线段树优化dp单杀*900。最小和最大没有本质区别，这里只讨论最小的情况。设\(f_i\)表示前缀\(i\)的答案，显然是要枚举\(j\)使得\((j,i]\)合并成一段：\[f_i=\min\bigg(f_j+\lceil\dfrac{s_i-s_j}{x}\rceil\bigg)\]其中\(s_i=\sum_{i......
  • P6109 [Ynoi2009] rprmq1
    优美的数据结构题。这题先修改再查询，基本明确了要使用扫描线做这道题。我们将第一维视为时间，那么我们对于一个操作，将其变为时刻\(l_1\)时，在区间\([l_2,r_2]\)加上\(x\)，时刻\(r_1+1\)时，在区间\([l_2,r_2]\)减去\(x\)。然后对于一个查询，相当于是要求区间\([l_2,r_2]\)......
  • 24.10.4-2
    虽然想着不就是没有朋友吗，我怎么能为这点事情去送死呢，但是内心还是非常不舒服我的人生意义到底是什么财富，美食，兴趣？这些其实完全不感兴趣食物只是维持生理活动的必需品罢了，如果不是必须吃，我宁愿不吃。财富所能满足的人不是欲望十足，就是野心十足，反正对我来说也只是维持生命的必......
  • 10.3 - AM - 模拟赛 总结
    复盘T1很水，一道异或求和，但是某两位仁兄因没打括号而死。T2很水，一道字符串处理，但是我和某位仁兄因没特判而死（虽然没有hack掉我，所以我理论上还是满分）。T3不水，看了很久，没想出来，自闭了就去看了T4。发现也做不出来。此时我出去晃了一圈，大概是不知道从哪里看到了一个“二”字......
  • 为 Windows 10/11 生成 autounattend.xml 文件 (schneegans.de)
    为Windows10/11生成autounattend.xml文件(schneegans.de)界面语言使用简体中文、格式、键盘x64跳过windows11安装需求检查(例如TPM、SecureBoot、电脑名称自动生成(想指定的,自己动手制作时区设置(默认根据第1条设置硬盘分区(擦除整个硬盘空间,并重新分区......
  • 10 月 3 日解题报告
    10月3日题解Tasklist[T1]ARC_134_C[T2]ARC_108_D[T3]ARC_137_C[T4]ARC_064_E[T1]ARC_134_CTheMajority题目因为原翻译有些重点并没有点出来，所以这里给出原题直译而不是带有《原神》游戏专业术语的转译版本。有编号为\(1\)到\(K\)的\(K\)个盒子。最初，所有......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99