2023暑假训练-part1

20230702

今天回来主要打了牛客的周赛

感觉就是DIV4水平，但是自己回寝室都八点了打了半个小时就结束了，实际上多个10min就AK了。

牛客周赛 牛客周赛 Round 1

A

题目大意：画一个大小为 $n$ 的 ‘u’

直接模拟即可：

#include<bits/stdc++.h>

using namespace std;

int n;

int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n*3;i++)
	{
		for(int j=1;j<=n;j++) cout<<'*';
		for(int j=1;j<=2*n;j++) cout<<'.';
		for(int j=1;j<=n;j++) cout<<'*';
		cout<<'\n';
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++) cout<<'.';
		for(int j=1;j<=n;j++) cout<<"*";
		for(int j=1;j<=2*(n-i);j++) cout<<".";
		for(int j=1;j<=n;j++) cout<<"*";
		for(int j=1;j<=i;j++) cout<<'.';
		cout<<'\n';
	}
	return 0;
}

B

游游拿到了一个数组，其中一些数被染成红色，一些数被染成蓝色。
游游想知道，取两个不同颜色的数，且它们的数值相等，有多少种不同的取法？

直接两个 map 即可

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int maxn=200200;

int ans=0;
int n;
int tot,a[maxn];
int val[maxn];
map <int,int> c1,c2;
int col[maxn];

signed main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>val[i];
	for(int i=1;i<=n;i++)
	{
		char tmp;
		cin>>tmp;
		if(tmp=='R') c1[val[i]]++;
		else c2[val[i]]++;
	}
	for(auto &v:c1) 
	{
		ans+=v.second*c2[v.first];
//		cout<<v.first<<' '<<v.second<<'\n';
	}
	cout<<ans<<endl;
	return 0;
}

C

游游拿到了一个01串（仅由字符’0’和字符’1’构成的字符串）。游游每次操作可以交换两个相邻的字符，例如，对于字符串"11001"而言，游游可以交换第二个字符和第三个字符变成"10101"。

考虑所有的情况，因为题目保证有解，如果 1 的个数为奇数个，并且 n 的为偶数个，那么一定是 10101 类似的情况，或者偶数个 1 以及 n 为奇数，一定是 01010 类似的情况

如果n为偶数的情况，那就有两种情况 010101 或者 101010 这两种情况，需要分别讨论。

显然不发生交叉的时候是最优的情况，因此我们直接按顺序移动 1 即可。

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int maxn=200200;

string s;
int n;
int place[maxn],cnt;
int ans;

signed main()
{
	ios::sync_with_stdio(false);
	cin>>s;
	n=s.size();
	for(int i=1;i<=n;i++)
	{
		if(s[i-1]=='1') place[++cnt]=i;
	}
	// n=2k
	ans=n*n;
	if(n%2==0)
	{
		int tans=0;
		for(int i=1;i<=n/2;i++)
		{
			int nowplace=i*2;
			tans+=abs(place[i]-nowplace);
		}
		ans=tans;tans=0;
		for(int i=1;i<=n/2;i++)
		{
			int nowplace=i*2-1;
			tans+=abs(place[i]-nowplace);
		}
		ans=min(ans,tans);
		cout<<ans<<endl;
	}
	else
	{
		if(cnt==n/2)
		{
			int tans=0;
			for(int i=1;i<=n/2;i++)
			{
				int nowplace=i*2;
				tans+=abs(place[i]-nowplace);
			}
			cout<<tans<<endl;
		}
		else
		{
			int tans=0;
			for(int i=1;i<=n/2+1;i++)
			{
				int nowplace=i*2-1;
				tans+=abs(place[i]-nowplace);
			}
			cout<<tans<<endl;		
		}
	}
	return 0;
}

D

给你一个数字串，询问有多少字串是9的倍数，可以包含前导0

这个就是记录 f[x] 表示当前模 9 余 x 的方案数，转移方程很简单。

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int maxn=200200;
const int modp=1e9+7;

string s;
int n;
int f[20],c[20];

signed main()
{
	ios::sync_with_stdio(false);
	cin>>s;
	n=s.size();
	for(int i=1;i<=n;i++)
	{
		char tmp=s[i-1];
		int v=tmp-'0';
		for(int j=0;j<=8;j++) c[j]=0;
		for(int j=0;j<=8;j++)
		{
			c[(j+v)%9]=(f[j]+f[(j+v)%9])%modp;
		}
		for(int j=0;j<=8;j++) f[j]=c[j];
		f[v%9]=(f[v%9]+1)%modp;
//		cout<<f[0]<<endl;
	}
	cout<<f[0];
	return 0;
}

20230706

中途进行了植物学实习，所以没有写代码。当天打了一场 CF 的 div2

CF1847

A.The Man who became a God

简单题，询问你 $n$ 个元素分成 $k$ 个区间（区间内元素编号必须连续），定义一个函数为 $f(l,r)=\sum_{i=l}^{r-1}\limits|a_{i}-a_{i+1}|$ 特别地 $l=r , f=0$

这个时候直接一个 dp 设 $f(x,y)$ 表示前 $x$ 个元素中分成 $y$ 个区间最小值，然后大力转移即可

#include<bits/stdc++.h>

using namespace std;

const int maxn=550;

int f[maxn][maxn],a[maxn];
int n,T,m;
int s[maxn];

int g(int x,int y)
{
	return s[y-1]-s[x-1];
}

int main()
{
	ios::sync_with_stdio(false);
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=1;i<=n;i++) s[i]=abs(a[i]-a[i+1])+s[i-1];
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		f[i][j]=0x3f3f3f3f;
		for(int i=1;i<=n;i++)
		f[i][1]=s[i-1];
		for(int i=1;i<=n;i++)
		for(int k=2;k<=m;k++)
		for(int j=1;j<i;j++)
		{
			f[i][k]=min(f[i][k],f[j][k-1]+g(j+1,i));
		}
		cout<<f[n][m]<<'\n';
	}
}

后记：其实直接取前 $k-1$ 个$a_i-a_{i+1}$ 就行了，写代码的时候傻逼了。

B. Hamon Odyssey

题目大意，定义一个函数$f(l,r) = a_l \& a_{l+1} \& a_{l+2} \& \ldots \& a_r$

然后给你一段序列，你需要把这个序列分最多的区间（不分也可以）,并且使得它们的和做小。

显然$f(x,y)\leq f(x,y+1)$ 也就是说 $f(1,n)$ 肯定是最大的。

如果它是 0 我们才考虑继续分。

#include<bits/stdc++.h>

using namespace std;

const int maxn=200200;

int a[maxn];
int n,T,m;
int s[maxn];

int g(int x,int y)
{
	return s[y-1]-s[x-1];
}

int main()
{
	ios::sync_with_stdio(false);
	cin>>T;
	while(T--)
	{
		cin>>n;
		int sz=0,tmp=0;
		for(int i=1;i<=n;i++) cin>>a[i];
		tmp=a[1];
		for(int i=1;i<=n;i++) tmp&=a[i];
		int bas=a[1];
		if(tmp!=0) 
		{
			cout<<1<<'\n';
			continue;
		}
		for(int i=1;i<=n;i++)
		{
			if(bas==-1) bas=a[i];
			bas&=a[i];
			if(bas==tmp) sz++,bas=-1;			
		}
		cout<<sz<<'\n';
	}
}

C. Vampiric Powers, anyone?

给你一段序列，假设长度为 $m$ 你可以进行以下操作:

任选一个 i ，然后让 $a_{m+1} = a_i \oplus a_{i+1} \oplus \ldots \oplus a_m,$

此操作无限次使用。

首先我们考虑这个的实际意义。就是把一个序列对称了一下，比如原来的字符串是这样的：

abcde

显然我们引入操作，假设i=3 原来的数组可以变成

abcde(cde)

这时候我们再取i=2

abcde(cde)(cde)edcb

我们可以得到
b,bc,bcd,bcde我们可以任意这样操作，可以得到任意一个区间，原问题就转化成了找到一个区间使得区间异或和最大

#include<bits/stdc++.h>

using namespace std;

const int maxn=200200;

bool l[maxn][280];
int a[maxn];
int n,T;

int main()
{
	ios::sync_with_stdio(false);
	cin>>T;
	while(T--)
	{
		cin>>n;
		map <int,int> m1,m2;
		for(int i=1;i<=n;i++) cin>>a[i];
		int tmp=0;
		l[0][0]=1;
		for(int i=1;i<=n;i++)
		for(int j=0;j<=255;j++)
		{
			l[i][j]=0;
		}
		for(int i=1;i<=n;i++)
		{
			l[i][a[i]]=1;
			for(int j=0;j<=255;j++)
			{
				l[i][j]=max(l[i-1][j^a[i]],l[i][j]);
			}
		}
		int ans=0;
		for(int i=1;i<=n;i++)
		for(int j=0;j<=255;j++)
		{
			if(l[i][j]) ans=max(ans,j);
		}
		cout<<ans<<endl;
	}
}

20230707

Codeforces Round 883 (Div. 3)

c 和 e2 被 hack 了，大寄.

由于 A,B 太水了，不写这俩题

C. Rudolf and the Another Competition

$n$ 个人参加acm赛制，第 i 人解决第 j 题花 $a_{i,j}$ 时间，罚时规定为每个问题被解决的时间之和，最后问你第 $1$ 个人的排名。

很显然直接排序贪心从最简单的问题开始做，但是注意有并列的情况需要考虑（我这边直接又按编号排序，相当于第一个人就是并列的名次）

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int maxn=200200;

int T,n,m,h;
int ans=0;
int a[maxn];

struct mmm{
	int psolv,tm,bh;
	bool operator < (const mmm &b)
	{
		if(psolv==b.psolv) 
		{
			if(tm==b.tm) return bh<b.bh;
			return tm<b.tm;
		}
		return psolv>b.psolv;
	}
}q[maxn];

signed main()
{
	ios::sync_with_stdio(false);
	cin>>T;
	while(T--)
	{
		cin>>n>>m>>h;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				cin>>a[j];
			}
			sort(a+1,a+m+1);
			int bast=0,sol=0;
			int tm=0;
			for(int j=1;j<=m;j++)
			{
				bast+=a[j];
				if(bast>h) 
				{
					break;
				}
				tm+=bast;
				sol++;
			}
			q[i].bh=i;
			q[i].psolv=sol;
			q[i].tm=tm;
		}
		sort(q+1,q+n+1);
		for(int i=1;i<=n;i++)
		{
			if(q[i].bh==1)
			{
				cout<<i<<'\n';
				break;
			}
		}
	}
}

D. Rudolph and Christmas Tree

计算面积题，如果两个三角形有交叉一定可以看成一个梯形和三角形，没什么说的。

#include<bits/stdc++.h>

using namespace std;

const int maxn=200200;

int n,T;
int d,h;
int a[maxn];
double s;

double checks(int x)
{
	double s=0;
	if(x==n)
	{
		s=d;
		s=s/2.0*h;
	}
	else
	{
		int deltah=a[x+1]-a[x];
		if(deltah>=h)
		{
			s=d;
			s=s/2.0*h;
		}
		else
		{
			double sd=d-d*(1.0*deltah/h);
			sd=sd/2+d*1.0/2;
			sd=sd*deltah;
			s=sd;
			
		}
	}
	return s;
}

int main()
{
	cin>>T;
	while(T--)
	{
		s=0;
		cin>>n>>d>>h;
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=1;i<=n;i++) s+=checks(i);
		cout<<setiosflags(ios::fixed)<<setprecision(7)<<s<<endl; 
	}
}

E. Rudolf and Snowflakes

询问 $n$ 是不是一个 $k$叉树分叉两次以上的顶点个数

换句话说，k进制下表示，一定是 111 这种情况。

对于 111 相当于解一元二次方程

对于 1111 可以提前枚举放进一个map，也可以二分，但是二分有点血流成河别忘了特判

对于 11111 以上的，暴力即可。

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int maxn=200200;

int n,T;
int d,h;
int a[maxn];
double s;

int check(int x)
{
	int tmp=n;
	while(tmp%x==1) tmp/=x;
	if(!tmp) return 1;
	else return 0;
}

signed main()
{
	cin>>T;
	map <int,int> mp;
	for(int i=2;i<=1e6;i++) mp[i*i*i+i*i+i+1]=1;
	for(int i=2;i*i*i*i+i*i*i+i*i+i+1<=1e18;i++) mp[i*i*i*i+i*i*i+i*i+i+1]=1;
	while(T--)
	{
		cin>>n;
//		if(n%2==0) 
//		{
//			cout<<"NO\n";
//			continue;
//		}
		int bj=0;
		for(int i=2;i*i*i*i*i+i*i*i*i+i*i*i+i*i+i+1<=n;i++) 
		{
			if(check(i)) bj=1;
			if(bj) break;
		}
		if(n>=7&&!bj)
		{
			unsigned int delta=1+4*(n-1);
			unsigned int tmp=sqrtl(delta);
			if(tmp*tmp!=delta) bj=0;
			else if(tmp%2==1ull) bj=1; 
//			if((2*n-1)%2==0) bj=1;
		}
		if(n>=7&&!bj)
		{
			if(mp[n]) bj=1;
		}
		if(!bj) cout<<"NO\n";
		else cout<<"YES\n";
		
	}
}

G. Rudolf and CodeVid-23

简单板子题，用 dij 思想即可。

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int maxn=2050;

int n,m,T;
int f[maxn];
int bas;
int sol[maxn],bd[maxn],vis[maxn];
int d[maxn];

int check(int x)
{
	int tmp=n;
	while(tmp%x==1) tmp/=x;
	if(!tmp) return 1;
	else return 0;
}

int getr()
{
	int ans=0;
	char t;
	for(int i=1;i<=n;i++)
	{
		ans<<=1;
		cin>>t;
		ans+=t-'0';
	}
	return ans;
}

signed main()
{
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		for(int i=0;i<(1<<n);i++) f[i]=0x3f3f3f3f,vis[i]=0;
		bas=getr();
		f[bas]=0;
		for(int i=1;i<=m;i++)
		{
			cin>>d[i];
			sol[i]=getr();
			bd[i]=getr();
		}
		priority_queue<pair<int,int>> q;
		q.push(make_pair(-f[bas],bas));
		while(!q.empty())
		{
			int t=q.top().second;
			q.pop();
			if(vis[t]) continue;
			vis[t]=1;
			for(int i=1;i<=m;i++)
			{
				int s=t-(t&sol[i]);
				int b=s|bd[i];
				if(f[b]>f[t]+d[i]) 
				{
					f[b]=f[t]+d[i];
					q.push(make_pair(-f[b],b));
				}
			}
		}
		if(f[0]==0x3f3f3f3f) cout<<"-1\n";
		else cout<<f[0]<<'\n';
	}
}