题目： http://codeforces.com/gym/101630
E
A young hero is starting his heroic life. The wise wizard suggested him an easy first quest. During this quest our young hero meets n magical creatures, in specific order. In order to help the young hero, the wizard gave him a clue — a list of n integers ai.
• If ai is positive, then the i-th magical creature is benevolent and gives to our hero one magical item of type ai. The hero can keep several items of the same type.
• If ai is negative, then the i-th magical creature is evil and in order to defeat it the young hero needs one magical item of type −ai. All magical items are fragile and can be used only once.
• If ai is zero, then the i-th creature is a unicorn. It gives the hero any magical item he asks for, but only one.
Your task is to help the young hero to finish the first quest, defeating all enemies on the way, or say that it is impossible.
Input
The first line of input contains one integer n (1 ≤ n ≤ 1000). The second line contains n integers ai (−1000 ≤ ai ≤ 1000).
Output
If it is impossible to defeat all enemies, then output one string “No”. If it is possible, then output string “Yes”, and in the next line output the types of items the hero should ask the unicorns for, in order they meet during the quest. Types must be integers in range from 1 to 1000 inclusive. If there are several solutions, output any of them.
Examples
input output
10 1 0 -4 0 0 -1 -3 0 -1 -2
Yes
4 1 3 2
5 5 8 0 -6 -3
No
3 2 -2 -2
No
题意： 给你一串数字，0可以随意变换 正数和负数不能变 要求每一个负数都能被抵消（前提是每一个负数只能被他前面的正数或者是0 抵消）
能全部抵消则输出YES 并按顺序输出0变换的正数 （答案多种）
思路：简单题，直接写代码
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<set> #include<algorithm> #include<map> #define maxn 200005 using namespace std; vector<int>zz; int main() { int n; int a[1005]; cin>>n; int ans=0; int aa[1005],c[1005]; //memset(aa,0,sizeof(aa)); int m=0; int p=0; for(int i=1;i<=n;i++) { cin>>a[i]; } //if(p==0&&m!=0){cout<<"NO"<<endl;return 0;} memset(aa,0,sizeof(aa)); for(int i=1;i<=n;i++){ if(a[i]>0)aa[a[i]]++; else if(!a[i]) { ans++; } else if(!aa[-a[i]]&&!ans) { cout<<"No"<<endl; return 0; } else if(aa[-a[i]]) aa[-a[i]]--; else ans--, zz.push_back(-a[i]); } while (ans--) zz.push_back(1); cout<<"Yes"<<endl; int flag=0; for(int i=0;i<zz.size();i++) { flag=1; if(i==0)cout<<zz[i]; else cout<<" "<<zz[i]; } if(flag==1) cout<<endl; return 0; }
Bella is working in a factory that produces boxes. All boxes are in a shape of rectangular parallelepipeds. A net of the corresponding parallelepiped is cut out of a flat rectangular piece of cardboard of size w×h. This net is a polygon with sides parallel to the sides of the rectangle of the cardboard. The net is bent along several lines and is connected along the edges of the resulting parallelepiped to form a box. The net is bent only along the edges of the resulting box.
The first example
The third example
Bella is a software developer and her task is to check whether it is possible to make a box of size a×b×c out of a cardboard of size w × h. Bella did write a program and boxes are being produced. Can you do the same? Input
The first line contains three integers a, b, and c — the dimensions of the box. The second line contains two integers w and h — the width and the height of the cardboard. All integers are positive and do not exceed 108.
Output
Print “Yes” if it is possible to cut a box a×b×c out of a cardboard of size w ×h. Print “No” otherwise.
Examples
input output
1 2 3
6 5
Yes
1 2 3
5 5
No
1 1 1
10 2
Yes
Note
There are 11 different nets of a cube, ignoring rotations and mirror images.
题意：输入 a b c和x y 问长为x宽为y的长方形能否折出长宽高分别为 a b c的长方体
思路：不是我写的，，但感觉应该只是考虑所有情况暴力
代码：
#include<stdio.h> int s[5],lg[5]; int lg1; int w,h; int a1,b1,c1; void check(int a,int b,int c) { int i,j; i=2*(a+b); j=c+2*a; if(i<j) { i=i^j; j=i^j; i=i^j; } //printf("%d %d ",i,j); if(i<=w&&j<=h) lg1=1; i=3*a+b+c; j=b+c; //printf("%d %d ",i,j); if(i<=w&&j<=h) lg1=1; i=2*a+b+c; j=a+b+c; //printf("%d %d ",i,j); if(i<=w&&j<=h) lg1=1; } int dfs(int k) { int i,j; if(k==3) { check(a1,b1,c1); return 0; } for(i=0;i<=2;i++) { if(!lg[i]) { lg[i]=1; if(k==0) a1=s[i]; else if(k==1) b1=s[i]; else if(k==2) c1=s[i]; dfs(k+1); lg[i]=0; } } return 0; } int main() { lg1=0; scanf("%d%d%d",&s[0],&s[1],&s[2]); scanf("%d%d",&w,&h); if(w<h) { w=w^h; h=w^h; w=w^h; } dfs(0); if(lg1) printf("Yes "); else printf("No "); return 0; }
Problem C. Connections
Time limit: 3 seconds
Hard times are coming to Byteland. Quantum computing is becoming mainstream and Qubitland is going to occupy Byteland. The main problem is that Byteland does not have enough money for this war, so the King of Byteland Byteman 0x0B had decided to reform its road system to reduce expenses. Byteland has n cities that are connected by m one-way roads and it is possible to get from any city to any other city using these roads. No two roads intersect outside of the cities and no other roads exist. By the way, roads are one-way because every road has a halfway barrier that may be passed in one direction only. These barriers are intended to force enemies to waste their time if they choose the wrong way. The idea of the upcoming road reform is to abandon some roads so that exactly 2n roads remain. Advisers of the King think that it should be enough to keep the ability to get from any city to any other city. (Maybe even less is enough? They do not know for sure.) The problem is how to choose roads to abandon. Everyone in Byteland knows that you are the only one who can solve this problem.
Input
Input consists of several test cases. The first line of the input contains the number of tests cases. The first line of each test case contains n and m — the number of cities and the number of roads correspondingly (n ≥ 4, m > 2n). Each of the next m lines contains two numbers xi and yi denoting a road from city xi to city yi (1 ≤ xi,yi ≤ n, xi 6= yi). It is guaranteed that it is possible to get from any city to any other city using existing roads only. For each pair (x,y) of cities there is at most one road going from city x to city y and at most one road going from city y to city x. The solution is guaranteed to exist. The sum of m over all test cases in a single input does not exceed 100000.
Output
For each test case output m − 2n lines. Each line describes a road that should be abandoned. Print the road in the same format as in the input: the number of the source city and the number of the destination city. The order of roads in the output does not matter, but each road from the input may appear in the output at most once and each road in the output must have been in the input. It still must be possible to get from any city to any other city using the remaining roads.
Example
input output illustration
1
4 9
1 2
1 3
2 3
2 4
3 2
3 4
4 1
4 2
4 3
输出
1 3
题意：给定一个有向图，顶点数为n 边为 m 问去掉哪 m-n*2 条边能使图依然保持连通性
思路： 正向和反向建图，，分别遍历1到各点 如果两次遍历都能遍历同一条边，，则那条边是不需要的，直接输出就好
代码：
#include<iostream> #include<cstdio> #include <bits/stdc++.h> #include<cstring> #include<cmath> #include<queue> #include<set> #include<algorithm> #include<map> #define maxn 200005 using namespace std; typedef pair<int,int>zz; vector<zz>mp1[100005],mp2[100005]; bool vis[maxn],ans[maxn]; int x[maxn],y[maxn]; void dfs(int x,vector <zz> *mp) { vis[x]=true; for(int i=0;i<mp[x].size();i++){ zz c=mp[x][i]; if (!vis[c.first]){ ans[c.second]=true; dfs(c.first, mp); } } // return ; } int main() { int t; int n,m; cin>>t; while(t--) { cin>>n>>m; memset(ans,false,sizeof(ans)); for(int i=0;i<n;i++) { mp1[i].clear(); mp2[i].clear(); } for(int i=0;i<m;i++) { cin>>x[i]>>y[i]; mp1[x[i]].push_back(make_pair(y[i],i)); mp2[y[i]].push_back(make_pair(x[i],i)); } memset(vis,false,sizeof(vis)); dfs(1,mp1); memset(vis,false,sizeof(vis)); dfs(1,mp2); for (int i = 0, cnt=m-(n*2); i < m && cnt; i++){ if (!ans[i]){ printf("%d %d ", x[i], y[i]); cnt--; } } } return 0; }
只会写这三题