Codeforces Beta Round #31 (Div. 2, Codeforces format)
http://codeforces.com/contest/31
A
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define pb push_back
#define maxn 1000005
typedef long long ll;
typedef unsigned long long ull;
/*#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif */ int a[]; int main(){
#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=;i<=n;i++) cin>>a[i];
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
for(int k=;k<=n;k++){
if(i!=j&&j!=k){
if(a[i]==a[j]+a[k]){
cout<<i<<" "<<j<<" "<<k<<endl;
return ;
}
}
}
}
}
cout<<-<<endl;
}
B
模拟
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define pb push_back
#define maxn 1000005
typedef long long ll;
typedef unsigned long long ull;
/*#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif */ int a[]; int Check(string str){
int pre=-;
int pos=-;
for(int i=;i<str.length();i++){
if(str[i]=='@'){
pos=i;
if(pre<i-&&i+<str.length()){
pre=i+;
}
else{
return -;
}
}
}
return pos;
} int main(){
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
string str;
cin>>str;
int pos=Check(str);
if(pos!=-){
for(int i=;i<str.length();i++){
cout<<str[i];
if(str[i]=='@'){ if(pos!=i){
cout<<str[i+];
i++; if(i<str.length()-){
cout<<',';
}
}
}
}
}
else cout<<"No solution"<<endl;
}
C
暴力
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define pb push_back
#define maxn 1000005
typedef long long ll;
typedef unsigned long long ull;
/*#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif */
struct sair{
int s,e,pos;
}a[]; bool cmp(sair a,sair b){
if(a.s==b.s) return a.e<b.e;
return a.s<b.s;
} int main(){
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=;i<n;i++){
cin>>a[i].s>>a[i].e;
a[i].pos=i+;
}
sort(a,a+n,cmp);
vector<int>ans;
int flag;
for(int i=;i<n;i++){
int pre=-;
flag=;
for(int j=;j<n;j++){
if(i!=j){
if(pre==-){
pre=a[j].e;
}
else{
if(pre>a[j].s){
flag=;
}
else{
pre=a[j].e;
}
}
}
}
if(!flag){
ans.pb(a[i].pos);
}
}
cout<<ans.size()<<endl;
sort(ans.begin(),ans.end());
for(int i=;i<ans.size();i++){
cout<<ans[i]<<" ";
}
}
D
bfs求连通块，模拟剪纸的过程
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define pb push_back
#define maxn 1000005
typedef long long ll;
typedef unsigned long long ull;
/*#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif */ int n,m,k;
int book[][];
int dir[][]={,,,,,-,-,}; int bfs(int x,int y){
queue<pair<int,int> >Q;
int ans=;
book[x][y]=;
Q.push(make_pair(x,y));
pair<int,int>p;
while(!Q.empty()){
p=Q.front();
Q.pop();
for(int i=;i<;i++){
int xx=p.first+dir[i][];
int yy=p.second+dir[i][];
if(xx>=&&xx<=*n&&yy>=&&yy<=*m&&!book[xx][yy]){
book[xx][yy]=;
if((xx%)&&(yy%)){
ans++;
}
Q.push(make_pair(xx,yy));
}
}
}
return ans;
} int main(){
#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
cin>>n>>m>>k;
int a,b,c,d;
while(k--){
cin>>a>>b>>c>>d;///边为偶数
a*=,b*=,c*=,d*=;
if(a==c){
if(b>d) swap(b,d);
for(int i=b;i<=d;i++){
book[a][i]=;
}
}
else{
if(a>c) swap(a,c);
for(int i=a;i<=c;i++){
book[i][b]=;
}
}
}
vector<int>ans;
for(int i=;i<=*n;i++){
for(int j=;j<=*m;j++){
if(!book[i][j]&&(i%)&&(j%)){
ans.pb(bfs(i,j));
}
}
}
sort(ans.begin(),ans.end());
for(int i=;i<ans.size();i++){
cout<<ans[i]<<" ";
}
cout<<endl;
}
E
题意：给2*n个数字，A和B各选n个各组成一个数，使得A+B的和最大
DP,细节在代码里
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define pb push_back
#define maxn 1000005
typedef long long ll;
typedef unsigned long long ull;
/*#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif */ ll dp[][];
ll p[]; int main(){
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
int n;
string str;
cin>>n;
cin>>str;
int len=*n;
p[]=;
for(int i=;i<=;i++){
p[i]=p[i-]*;
}
///dp[i][j] 表示A选了i个，B选了j个,dp[i][j]记录的是A+B的和
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
ll tmp=str[*n-i-j]-'';///从后向前推
if(i){
dp[i][j]=dp[i-][j]+tmp*p[i-];
}
if(j){
dp[i][j]=max(dp[i][j],dp[i][j-]+tmp*p[j-]);
}
cout<<dp[i][j]<<endl;
}
}
int i=n,j=n;
while(i||j){
ll tmp=str[*n-i-j]-'';
if(i>&&(tmp*p[i-]+dp[i-][j]==dp[i][j])){
cout<<'H';
i--;
}
else{
cout<<'M';
j--;
}
}
cout<<endl;
}