CF Round 87

程序员文章站 2022-07-12 22:30:52

...

文章目录

A. Alarm Clock
B. Ternary String
C1. Simple Polygon Embedding
C2. Not So Simple Polygon Embedding
D. Multiset
E. Graph Coloring
F. Summoning Minions
G. Find a Gift

A. Alarm Clock

time limit per test: 2 seconds memory limit per test: 256 megabytes

题意：

给出 $a,b,c,d~(1 \leq a,b,c,d \leq 10^9)$ ，Polycarp 一开始先睡 $b$ 分钟，然后从第 $b$ 分钟开始闹钟每隔 $c$ 分钟响一次，Polycarp 醒来之后若总睡眠时间达到 $a$ 分钟以上，则直接起床，否则继续睡，但他每次得花 $d$ 分钟才能睡着；问能否睡够 $a$ 分钟，若可以输出总花费时间，若不能输出 $-1$ ；

$t~(1 \leq t \leq 1000)$ 组测试数据；

分析：

模拟，考虑几种情况：

若 $b>=a$ ，则花费即 $b$ ；
若 $b<a$ 且 $c<=d$ ，则无解；
若 $b<a$ 且 $c>d$ ，则从第 $b$ 分钟之后每 $c$ 分钟补充 $c-d$ 分钟睡眠时间；

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	ll t,a,b,c,d;
	cin>>t;
	while(t--)
	{
		cin>>a>>b>>c>>d;
		if(a<=b) cout<<b<<endl;
		else if(c<=d) cout<<-1<<endl;
		else{
			ll res=b; a-=b;
			ll sub=c-d;
			ll tim=a/sub; if(a%sub) tim++;
			res+=tim*c;
			cout<<res<<endl;
		} 
	} 
}

B. Ternary String

time limit per test: 2 seconds memory limit per test: 256 megabytes

题意：

给出一个仅包含 $1,2,3$ 的字符串 $s~(1 \leq |s| \leq 200000)$ ，求最短的连续区间，使得这个区间内都出现过 $1,2,3$ ，输出这个最短的长度，无解输出 $0$ ；

$t~(1 \leq t \leq 20000)$ 组测试数据；

分析：

可以二分或者单调栈，二分的话需要维护一下 $1,2,3$ 出现的前缀和；

二分

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)

const int N = 2E5+10;
string s; 
int a[N],b[N],c[N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t,n;
	cin>>t;
	while(t--)
	{
		cin>>s; n=s.length();
		rep(i,0,n) a[i]=b[i]=c[i]=0;
		rep(i,1,n) 
		{
			int x=s[i-1]-'0';
			if(x==1) a[i]=1;
			if(x==2) b[i]=1;
			if(x==3) c[i]=1;
		}
		rep(i,2,n) a[i]+=a[i-1],b[i]+=b[i-1],c[i]+=c[i-1];
		int L=3,R=n,ans=0;
		while(L<=R)
		{
			int m=(L+R)>>1;
			int ok=0;
			rep(i,1,n)if(i+m-1>n) break;
			else{ int k=i+m-1;
				if(a[k]-a[i-1]&&b[k]-b[i-1]&&c[k]-c[i-1])
				{
					ok=1;break;
				}
			}
			if(ok) ans=m,R=m-1;
			else L=m+1; 
		}
		cout<<ans<<endl;
	}
}

单调栈

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++) 

string s;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t,n;
	cin>>t;
	while(t--)
	{
		cin>>s; n=s.length();
		int ANS=n+1,num[4]={0},cnt=0;
		rep(i,0,n-1)
		{
			int x=s[i]-'0';
			num[x]++;
			cnt++;
			while(num[1]&&num[2]&&num[3])
			{
				int pre=i-cnt+1;
				x=s[pre]-'0';
				if(num[x]>1) num[x]--,cnt--; 
				else break;
			}
			if(num[1]&&num[2]&&num[3]) ANS=min(ANS,cnt);
			if(ANS==3) break;	
		}
		if(ANS>n) cout<<0<<endl;
		else cout<<ANS<<endl;
	}
}

C1. Simple Polygon Embedding

time limit per test: 2 seconds memory limit per test: 256 megabytes

题意：

给出 $n~(n \in even 且 2 \leq n \leq 200)$ ，求能完全容纳下正 $2*n$ 多边形的正方形的最短边长； $T~(1 \leq T \leq 200)$ 组测试数据；

分析：

$n \in even$ ，所以 $2*n$ 显然是 $4$ 的倍数，再套来官方题解的图

CF Round 87

所以不难理解，最短边长就是 $2 \times MN$ ，即 $ans=\frac{1}{tan\frac{\pi}{2\cdot n}}$ ，推一遍
$ans=2 \times\frac{0.5}{tan \angle M}=\frac{1}{tan \frac{2 \cdot \pi}{2 \cdot n \cdot 2}}=\frac{1}{tan\frac{\pi}{2\cdot n}}$

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)

const double PI = acos(-1.0); 

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t,n;
	cin>>t;
	while(t--)
	{
		cin>>n;
         double ans=1.0/tan(PI/(2*n));
		cout<<setprecision(10)<<ans<<endl;
	}
}

C2. Not So Simple Polygon Embedding

time limit per test: 2 seconds memory limit per test: 256 megabytes

题意：

和 $C1$ 唯一的不同点就是 $n \in odd~(3 \leq n \leq 199)$ ；

分析：

$n \in odd$ ，所以 $2*n$ 不再是 $4$ 的倍数，但因为仍是正偶数多边形( $2n>4$ )，所以肯定可以通过旋转使得有 $4$ 个点正好卡在正方形的四条边上，再套图

CF Round 87

所以需要求第一张图到第二张图的旋转角度；再观察，图一和图三是等价的，所以旋转角度为 $\frac{\angle O}{2}$ ，即 $ans=\frac{cos(\frac{\pi}{4n})}{\frac{\pi}{2n}}$ ；

(当时我没想到旋转角度正好是一半，直接二分角度的，也A了)

代码：(贴下二分的)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)

const double PI = acos(-1.0); 

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t,n;
	cin>>t;
	while(t--)
	{
		cin>>n; n*=2;
		double a=2*PI/(2*n);
		double L=0,R=a;
		rep(i,0,100)
		{
			double m=(L+R)/2;
			if(cos(m)>cos(a-m)) L=m;
			else R=m;
		} 
		double b=(PI-2*PI/n)/2;
		double len=0.5/cos(b);
		double ans=len*cos(L)*2;
		cout<<setprecision(10)<<ans<<endl;
	}
}

D. Multiset

time limit per test: 1.5 seconds memory limit per test: 28 megabytes

题意：

先给出 $n$ 和 $q~(1 \leq n,q \leq 10^6)$ ，接着给出初始大小为 $n$ 的多重集 $a~(1 \leq a_1 \leq a_2 \leq \cdots \leq a_n \leq n)$ ，再给出 $q$ 个操作，每个操作给出 $k_i$ ，分两种：

if $1 \leq k_i \leq n$ ，那么把 $k_i$ 加入多重集；
if $k_i<0$ ，那么就删除多重集中从小到大排第 $|k_i|$ 的数；

最后求经过 $q$ 次操作之后，多重集是否为空，是则输出 $0$ ，否则输出多重集内任意一个元素就可以了；

分析：

多重集为空的情况不难想，即 $操作2=操作1+n$ ；若不为空，仅要求输出任意一个集合内元素即可，看一看时限，考虑 $O(nlogn)$ 的做法；首先对于一个数 $m$ ，我们考虑有没有小于等于它的数最后还在多重集内，因为对 $m$ 产生影响的只能是小于等于它的数 (只有在多重集内添加或者删除小于等于 $m$ 的数才会对它的排序造成影响) ，所以判断即更新维护小于等于 $m$ 的数的数量 $O(n+m)$ ，二分这个 $m$ ，复杂度就达到要求了；(线段树和树状数组也可以)

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)

const int N = 1E6+10;

vector<int>a,b;
int n,q; 

int ask(int m)
{
	int cnt=0;
	for(auto v:a)if(v<=m)cnt++;  //初始多重集内<=m的数量

	for(auto v:b)
		if(v>0&&v<=m) cnt++;    //操作1添加v
	    else if(v<0&&abs(v)<=cnt) cnt--; //操作2删除第|v|个数
	return cnt; 
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin>>n>>q;
	a.resize(n);
	b.resize(q);
	rep(i,0,n-1)cin>>a[i];
	rep(i,0,q-1)cin>>b[i];
	
	if(ask(1e7)==0) cout<<0,exit(0);
	//相当于判断多重集是否为空
	
	int L=0,R=1e6+1,ans;
	while(R-L>1)
	{
		int m=(L+R)>>1;
		if(ask(m)>0) R=m;  //aks(m)>0,证明最后多重集中存在<=m的数，所以更新上界；
		else L=m;
	}
	cout<<R;
}

树状数组

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
const int N = 2E6+60;
 
int a[N],n,q;
 
int lowbit(int x){return x&(-x);}
 
void add(int x,int k){
	for(int i=x;i<N;i+=lowbit(i)) a[i]+=k;
}
 
ll query(int x){
	ll res=0;
	for(int i=x;i;i-=lowbit(i)) res+=a[i];
	return res;
}
 
void del(int x){
	int res=0;
	for(int i=19;i>0;i--)
	  if(a[res|(1<<i)]<x) x-=a[res|=(1<<i)];
	if(a[res|1]<x) add(res+2,-1);
	else add(res+1,-1);
}
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin>>n>>q;
	rep(i,1,n){
		int x;cin>>x;
		add(x,1);
	}
	rep(i,1,q){
		int x;cin>>x;
		if(x>0) add(x,1);
		else del(-x);
	}
	if(!query(n)) cout<<0,exit(0);
	rep(i,1,n) if(query(i)) cout<<i,exit(0);
}

E. Graph Coloring

time limit per test: 2 seconds memory limit per test: 256 megabytes

题意：

给顶点数为 $n$ 的无向图(可能不连通，有自环，重复边)，现在要求你把这张图染三色(颜色种类从1到3)，要求：

$n1,n2,n3$ 分别对应最后染色完三种颜色的数量；
对于每条边 $(u,v)$ 要求 $|col_u-col_v|=1$ ， $col_x$ 即顶点 $x$ 的颜色种类；

问是否存在合理的染色方式，不存在则输出 $NO$ ，否则输出 $YES$ 和具体方案；

分析：

有了条件 2 的限制，其实这里的染三色就相当于染双色(1,3一类)，所以判断这个图是否满足条件2 即判断这个图是否为二分图，判断就搜索一遍试着染色(双色)就可以了；然后想条件1，因为我们已经给图染双色了，而图可能是由若干个联通块组成的，所以这就是明显的分组背包了；

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
const int N = 5000+10;

int lab[N],be[N],cnt,A[N],B[N],ANS[N];
int n,n1,n2,n3,m;
bool dp[N][N];
vector<int>G[N];

bool dfs(int u,int nO)
{
	lab[u]=nO;  //第u个顶点的颜色
	be[u]=cnt;  //第u个顶点属于第几个联通块
	if(nO==1) A[cnt]++;  //第cnt个联通块颜色A的数量
	else B[cnt]++; //第cnt个联通块颜色B的数量
	for(auto v:G[u])
	{
		if(lab[v]==0){
			if(!dfs(v,3-nO))return 0;
		}
		else{
			if(lab[u]==lab[v]) return 0;
		}
	}
	return 1; 
} 

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin>>n>>m>>n1>>n2>>n3;
	rep(i,1,m){
		int u,v;cin>>u>>v;
		G[u].pb(v),G[v].pb(u); 
	}
	
	rep(i,1,n) if(!lab[i]){
		++cnt;  //第cnt个联通块
		if(!dfs(i,1)) cout<<"NO",exit(0);  //染色失败，无解
	}
	memset(dp,false,sizeof dp);
	dp[0][0]=1;
	rep(i,1,cnt)  //分组背包
	{
	    rep(k,A[i],n2) dp[i][k]|=dp[i-1][k-A[i]];
		rep(k,B[i],n2) dp[i][k]|=dp[i-1][k-B[i]];	
	}
	if(!dp[cnt][n2]) cout<<"NO",exit(0);
	
	cout<<"YES\n";
    int k=n2;
    //这里可以不用另外记录路径，只需要利用DP数组的性质就可以找到一条合理的路径(因为每个联通块至多只有两个选择)
    for(int i=cnt;i>=1;i--) 
    {
    	if(dp[i-1][k-A[i]]) ANS[i]=1,k-=A[i];
    	else ANS[i]=2,k-=B[i];
	}
	rep(i,1,n)
	{
		int num=ANS[be[i]];
		if(lab[i]==num) cout<<2;
		else if(n1) cout<<1,n1--;  //1,3是一类的，所以用完了1剩下的用3就可以了
		else cout<<3;
	}
}

F. Summoning Minions

time limit per test: 6 seconds memory limit per test: 512 megabytes

题意：

$n$ 张牌，最多选 $k$ 张，可以选了之后再删 $(1 \leq k \leq n \leq 75)$ ；每张牌初始战力值为 $a_i$ ，选第 $i$ 张牌可以给之前选的牌(删去的不算)的战力值都加上 $b_i$ ，求一种具体的选删方式，使得最后的 $k$ 张牌的战力值总和最大；

分析：

稍微想一下，肯定是先选择 $k-1$ 张牌，然后不断选删第 $k$ 张直到最后，那么为了最大化战力值总和，所以 $b$ 大的肯定先放后面；所以先按照 $b$ 值排升序，然后 dp[i][j] 表示排序后前 $i$ 张牌，选中 $j$ 张的最大战力值(这里的选中意思是这 $j$ 张牌在最后的 $k$ 张牌中)

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define frep(i,a,b) for(int i=a;i>=b;i--)
const int N = 75+5;

int dp[N][N];
bool path[N][N],mark[N];
struct node{
	int a,b,id;
	bool operator < (const node& x)const{return b<x.b;}
}e[N];

int main()
{
    ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t,n,k;cin>>t;
	while(t--)
	{
		cin>>n>>k;
		rep(i,1,n)cin>>e[i].a>>e[i].b,e[i].id=i;
		sort(e+1,e+n+1);
		memset(dp,-1,sizeof(dp));
		memset(path,0,sizeof(path));
		memset(mark,0,sizeof(mark));
		
		dp[0][0]=0;
		rep(i,1,n)rep(j,0,min(i,k))
		{
			if(dp[i-1][j]>=0)
			    dp[i][j]=dp[i-1][j]+e[i].b*(k-1); //这张牌不属于最后k张牌之一
			if(j>0&&dp[i-1][j-1]>=0&&dp[i][j]<dp[i-1][j-1]+e[i].a+e[i].b*(j-1))
			{
			    dp[i][j]=dp[i-1][j-1]+e[i].a+e[i].b*(j-1);
				path[i][j]=1;	
			}	
		}
		int j=k;
		frep(i,n,1)if(path[i][j]) mark[e[i].id]=1,j--;
		cout<<k+(n-k)*2<<endl;
		int end,cnt=0;;
		rep(i,1,n)if(mark[e[i].id]){
		    if(++cnt==k) {end=e[i].id;break;}
		    cout<<e[i].id<<' '; 
		}
		rep(i,1,n)if(!mark[e[i].id])cout<<e[i].id<<' '<<-e[i].id<<' '; 
	    cout<<end<<endl;
	}
}

G. Find a Gift

time limit per test: 2 seconds memory limit per test: 256 megabytes

题意： (交互题)

$n$ 个盒子， $k$ 个装有礼物，剩下的装有石头 $(2 \leq n \leq 1000,1 \leq k \leq \frac{n}{2})$ ，石头的重量完全相同，礼物的重量可能不相同但均小于石头；现在你有至多 $50$ 次机会询问任意两堆盒子的重量比较的结果，求第一个装有礼物的盒子的最小编号；

分析：

前 $30$ 次随机询问比较第 $1$ 个盒子和其它盒子的重量，若询问完还是 $1$ 号盒子最重，则它装有石头的概率就是
$p=1-(\frac{k-1}{n})^{30}>1-(\frac{1}{2})^{30}$
几乎为 $1$ ，所以这时可以确定 $1$ 号盒子装有石头，然后按 $2$ 的幂次比较： $[1,1] 和 [2,2] , [1,2] 和 [2,4] \cdots$ ，直到重量不等，则后面一堆必有装有礼物的盒子，再二分就可以了；

代码：

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
int n,k;

int ask(int l1,int r1,int l2,int r2)
{
	cout<<"? "<<r1-l1+1<<" "<<r2-l2+1<<endl;
	rep(i,l1,r1-1) cout<<i<<' ';cout<<r1<<endl;
	rep(i,l2,r2-1) cout<<i<<' ';cout<<r2<<endl;
	cout.flush();
	string s;cin>>s;
	if(s[0]=='F') return -1;
	if(s[0]=='E') return 0;
	if(s[0]=='S') return 1;
} 

void solve()
{
	srand(0);
	rep(i,1,30)
	{
		int cnt=2+rand()%(n-1);
		int ans=ask(1,1,cnt,cnt);
		if(ans==1)
		{
			cout<<"! 1\n";
			cout.flush();
			return;
		}
	} 
	
	int len=1;
	while(1)
	{
		if(len*2<=n){
	        int ans=ask(1,len,len+1,len*2);
			if(ans!=0) break;		
		}
		else{
			int ans=ask(1,n-len,len+1,n);
			if(ans!=0) break;
		}
		len<<=1;
	}
	
	int L=len+1,R=min(2*len,n);
	while(L<=R)
	{
		int m=(L+R)>>1;
		int ans=ask(1,m-L+1,L,m);
		if(ans==0) L=m+1;
		else R=m-1;
	}
	cout<<"! "<<L<<endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;cin>>t;
	while(t--)
	{
	    cin>>n>>k;
	    solve();
	}
	
}

CF Round 87

文章目录

A. Alarm Clock

B. Ternary String

C1. Simple Polygon Embedding

C2. Not So Simple Polygon Embedding

D. Multiset

E. Graph Coloring

F. Summoning Minions

G. Find a Gift

JavaScript中用于四舍五入的Math.round()方法讲解

qq浏览器审查元素方法分享 qq浏览器审核元素修改代码秒领CF礼包

CF1207G Indie Album

C# Math.Round()函数问题

POJ3252Round Numbers(数位dp)

cf1060E. Sergey and Subway(思维枚举)

CF1204D Kirk and a Binary String

PHP取整函数:ceil,floor,round,intval的区别详细解析

php取整函数ceil,floo,round的用法及介绍

CF月光宝盒使用教程(图解)

CF Round 87

文章目录

A. Alarm Clock

B. Ternary String

C1. Simple Polygon Embedding

C2. Not So Simple Polygon Embedding

D. Multiset

E. Graph Coloring

F. Summoning Minions

G. Find a Gift

JavaScript中用于四舍五入的Math.round()方法讲解

qq浏览器审查元素方法分享 qq浏览器审核元素修改代码秒领CF礼包

CF1207G Indie Album

C# Math.Round()函数问题

POJ3252Round Numbers(数位dp)

cf1060E. Sergey and Subway(思维 枚举)

CF1204D Kirk and a Binary String

PHP取整函数:ceil,floor,round,intval的区别详细解析

php取整函数ceil,floo,round的用法及介绍

CF月光宝盒使用教程(图解)

cf1060E. Sergey and Subway(思维枚举)