当前位置:   article > 正文

Codeforeces Educational Codeforces Round 109(A-D)部分_codeforeces educate round

codeforeces educate round

A. Potion-making

大概就是要问你要多少步,可以构造出来一个百分数.
比如构造出25%,那么就是1/(3+1),答案是4.
构造3%,就是3/(97+3) 答案是100.
很显然,答案是一个这样的形式 n/m.而且这个形式n和m不能互相约分,那么m就是这个答案,使用一下gcd进行约分即可.

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}
int main(){
	int T;cin>>T;
	while(T--){
		int n;cin>>n;
		int ans=100/gcd(100,n);
		cout<<ans<<endl;
	}
return 0;}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

B. Permutation Sort

题意:给你一个n的全排列的数组。你可以进行一个操作,就是挑选任意连续长度的数组(除了整个数组),任何对其中的数字位置进行任意安排(就是说可以让他们变得升序).问你最少进行多少次数组才能变得升序.
首先把最特殊的去掉,如果数组本身就是升序的,那么没有必要操作,输出0即可.
第二种情况,末尾是n或者开头有1(同时有的时候也一样).那么只用进行一次操作即可。这是因为排列是特殊的,你升序的话,开头必须是1,结尾也必须是n.如果这两个有一个是对的,那么就把其他部分只进行一次操作,就会变得有序.
第三种情况,开头是n并且结尾是1,由于规则,我们不能对整个数组直接进行操作。我们要花费两个操作把n与1从各自错误的位置中弄出来,再花费一个操作把他们排好序.答案是3.
其他情况,答案就是2.
代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 53;
int a[maxn];
bool judge(int n){
	bool flag=false;
	for(int i=0;i<n;i++){
		if(a[i]!=i+1) return false;
	}
	return true;
}
int main(){
	int T;cin>>T;
	while(T--){
		int n;scanf("%d",&n);
		for(int i=0;i<n;i++){
			scanf("%d",&a[i]);
		}
		int ans;
		if(judge(n)){
			ans=0;
		}
		else if (a[0]==1||a[n-1]==n) ans=1;
		else if(a[0]==n&&a[n-1]==1) ans=3;
		else ans=2;
		printf("%d\n",ans);
	}
return 0;}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

C.Robot Collisions

题意:给你n个机器人和它的坐标和它们的初始方向(向左或者向右).
问你每个机器人最少多久时间被碰到然后爆炸.
首先一个比较好发现的规律就是,奇数坐标的机器人只能取碰到奇数坐标的机器人,同理偶数也只能碰到偶数的.因为偶数和奇数同时经过一秒时,一定会交错地错开.那么把机器人按坐标的奇偶性分为两组.
然后按照机器人的初始朝向 分为四种情况分别讨论计算 有1. R L
2. R R 3. L L 4. L R
注意到,第一种情况应该是最快的.然后是2/3 最后是4.这是第一直觉.
接下来就是分类讨论和计算了,如下图.

在这里插入图片描述
得到四种情况的答案计算式子.接下来是主算法的思考,显然,L似乎是最重要的那一个,因为它的答案都比较小.这种操作类似于栈,每遇到一个L,如果栈非空,就把栈顶取出,计算答案. 根据栈顶R与L的方向不同,答案也随之不同.
如果遇到一个R方向的,就直接压栈,先不进行计算.因为我们发现L R的值非常大,是最大的,至少是m时间少一点. 而R R 则是m-(x1+x2).

在这里插入图片描述
然后是一些奇怪的想法对于第二个L来说,它会与左边的L相遇还是会与R先相遇呢,凭直觉,应该是与左边的L相遇,当然推一下没有问题。

进行完以上的操作后,若栈内还剩余多于1的元素,它们仍会相遇.但这时候又与上面的操作不同,因为在上面的操作中,我们是碰到一个L就会进行出栈计算.那么栈中一定没有L L 与 R L 类型 .只有 R R 与 R L类型.操作与上面类似,不过是进行了计算公式的变化.
本题难点在于想到用栈计算.然后确定L就是出栈计算 R就是压栈,最后在最后再去处理R R,L R的类型,因为它们是时间比较长的,在最后计算也没有影响.
代码:

#include<bits/stdc++.h>
using namespace std;
struct Node{
	int x,dr,id;
	bool operator < (const Node &rhs ) {
		return x<rhs.x;
	}
};
int main(){
	int T;cin>>T;
	while(T--){
		int n,m;cin>>n>>m;
		vector<Node> a(n);
		for(int i=0;i<n;i++){
			scanf("%d",&a[i].x);
			a[i].id=i;
		}
		for(int i=0;i<n;i++){
			char ch;cin>>ch;
			if(ch=='L') a[i].dr=0;
			else a[i].dr=1;
		}
		sort(a.begin(),a.end());
		vector<int> ans(n,-1);
		vector<vector<Node> > s(2);
		for(auto i : a){
			int k=i.x%2;
			if(i.dr){  // if i is the right direction, push it in the stack
				s[k].push_back(i);
			}
			else {          // if i is the left direction check the stack.
			if(!s[k].empty()){ // if the stack isn't empty ,calculate the ans
			   Node l = s[k].back();
			   s[k].pop_back();
			   int id1=l.id,id2=i.id;
			   if(l.dr) {   //the x1 is right direction
			   	ans[id1]=ans[id2]=(i.x-l.x)/2;
			   }
			   else ans[id1]=ans[id2]=(i.x+l.x)/2;      
			}
			else s[k].push_back(i);
		}
	}
	for(int i=0;i<2;i++){
		while(s[i].size()>1){
			Node r=s[i].back();s[i].pop_back();
			Node l=s[i].back();s[i].pop_back();
			if(l.dr){ //if x1 is right direction
				ans[l.id]=ans[r.id]=m-(l.x+r.x)/2;
			}
			else {
				ans[l.id]=ans[r.id]=m+(l.x-r.x)/2;
			}
		}
	}
	for(auto i : ans){
		printf("%d ",i);
	}
	cout<<endl;
	} 
return 0;}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61

D.Armchairs

题意:给你一个长为n的序列,序列里面每个数字要么是0,要么是1.输入保证1的数量不大于n/2. 然后你有一个操作,可以把1的位置挪到0去,花费是两者坐标的距离.
现在,题目询问你,把所有1的位置都挪到0的位置上去,最小的花费是多少.
思路:一开始是这么想的,使用费用流.建立超级源点s,然后每个点1,源点s都连向它.然后对于每一个1.与每一个0都有一条边,费用是二者距离.最后0连向汇点t.这样一共有n+2个结点 最坏是n^2的边数.题目的n很大,边数m会变得难以接受.所以要换一种建图方法.
新的建图方法:对于每个1,仍向之前那样建立源点s->1的边,费用为0,容量为1.对于每个0.建立0->t的边,费用为0,容量为1.
接下来是重点.每个相邻的两个点之间,都建立一条边(实际上是无向边).容量为INF(代表可以任意转换),费用为1.
这样问题就变成求解s,t的一个费用流 套用板子即可.

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5005;
const int INF = 1e9+7;
int ans=0;
struct Edge{
	int from,to,cap,flow,cost;
};
struct Node{
	int v,cost;
	bool operator < (const Node &rhs) const{
		return cost>rhs.cost;
	}
};
struct MCMF{
	int n,m,s,t;    
	vector<Edge> edges;vector<int> G[maxn];
	int vis[maxn],d[maxn],p[maxn],a[maxn];
	void init(int n){
		this->n=n;
		for(int i=0;i<n;i++) G[i].clear();
		edges.clear();
	}
	void addedge(int from,int to,int cap,int cost){
		edges.push_back((Edge){ from,to,cap,0,cost});
		edges.push_back((Edge){ to,from,0,0,-cost});
		m=edges.size();G[from].push_back(m-2);G[to].push_back(m-1);
	}
bool Dijkstra(int s,int t,int &flow,int &cost){
		for(int i=0;i<=n;i++) d[i]=INF;
		memset(vis,0,sizeof(vis));
		d[s]=0;p[s]=0;a[s]=INF;
		priority_queue<Node> Q;
		Q.push((Node){ s,0});
		while(!Q.empty()){
			int u=Q.top().v;Q.pop();
			if(vis[u]) continue;
			vis[u]=true;
			for(int i=0;i<G[u].size();i++){
				Edge &e=edges[G[u][i]];
				if(e.cap>e.flow&&d[e.to]>d[u]+e.cost){
					d[e.to]=d[u]+e.cost;
					p[e.to]=G[u][i];
					a[e.to]=min(a[u],e.cap-e.flow);
					Q.push((Node){ e.to,d[e.to]});
				}
			}
		}
		if(d[t]==INF) return false;
		flow+=a[t];cost+=d[t]*a[t];
		int u=t;
		while(u!=s){
			edges[p[u]].flow+=a[t];
			edges[p[u]^1].flow-=a[t];
			u=edges[p[u]].from;
		}
		return true;
	}
	int Mincost(int s,int t){ 
		int flow=0,cost=0;
		while(Dijkstra(s,t,flow,cost));
		ans=flow;
		return cost;
	}
};
MCMF g;
int seat[maxn];
int main(){
	int n;cin>>n;
	vector<int> v1;
	vector<int> v2;
	int s=0,t=n+1;
	g.init(n+3);
	for(int i=1;i<=n;i++){
		int temp;scanf("%d",&temp);
		if(temp>0) v1.push_back(i);
		else v2.push_back(i);
	}
	for(auto i : v1){
		g.addedge(0,i,1,0);
	}
	for(int i=1;i<=n;i++){
		if(i==1){
			g.addedge(i,i+1,INF,1);
		}
		if(i==n){
		g.addedge(i,i-1,INF,1);	
		}
		else {
		g.addedge(i,i-1,INF,1);
		g.addedge(i,i+1,INF,1); 
	}} 
	for(auto i : v2){
		g.addedge(i,t,1,0);
	}
	cout<<g.Mincost(s,t);
return 0;}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Monodyee/article/detail/698319
推荐阅读
相关标签
  

闽ICP备14008679号