Codeforces Beta Round #70 (Div. 2)
http://codeforces.com/contest/78
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 eb emplace_back
#define maxn 1000006
#define eps 1e-8
#define pi acos(-1.0)
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef unsigned long long ull; map<char,int>mp; int main(){
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
mp['a']=,mp['e']=,mp['i']=,mp['o']=,mp['u']=;
string str;
getline(cin,str);
int num=;
for(int i=;i<str.length();i++){
num+=mp[str[i]];
}
if(num==){
getline(cin,str);
num=;
for(int i=;i<str.length();i++){
num+=mp[str[i]];
}
if(num==){
getline(cin,str);
num=;
for(int i=;i<str.length();i++){
num+=mp[str[i]];
}
if(num==) {
cout<<"YES"<<endl;
return ; }
} }
cout<<"NO"<<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 eb emplace_back
#define maxn 1000006
#define eps 1e-8
#define pi acos(-1.0)
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef unsigned long long ull; map<char,int>mp; int main(){
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
int n;
cin>>n;
cout<<"ROYGBIV";
n-=;
for(int i=;i<n;i++){
if(i%==){
cout<<"G";
}
else if(i%==){
cout<<"B";
}
else if(i%==){
cout<<"I";
}
else {
cout<<"V";
}
}
}
C
博弈 如果n是偶数的话，后手必胜，因为他可以模仿先手，如果n是奇数的话，判断先手能否完成切割任务
#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 eb emplace_back
#define maxn 1000006
#define eps 1e-8
#define pi acos(-1.0)
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef unsigned long long ull; map<char,int>mp;
int n,m,k;
bool panduan(){
int sq=sqrt(m);
for(int i=;i<=sq;i++){
if(m%i==){
if(i>=k&&m/i>) return ;
else if(i>&&m/i>=k) return ;
}
}
return ; } int main(){
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
cin>>n>>m>>k;
if(n%==) cout<<"Marsel";
else {
if(panduan()){
cout<<"Timur";
}
else{
cout<<"Marsel";
} }
}
D
#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 eb emplace_back
#define maxn 1000006
#define eps 1e-8
#define pi acos(-1.0)
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef unsigned long long ull; map<char,int>mp;
int n,m,k; int main(){
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
ll n;
cin>>n;
ll ans=;
for(double i=8.0/;i<*n/sqrt();i+=){
double tmp=(sqrt(16.0*n*n/-*i*i)-i)/2.0-2.0/;
if(tmp>) ans+=(ll)tmp/+;
}
cout<<ans*+<<endl;
}
E
最大流。先标记毒气到达每个实验室的时间，再判断科学家能否在毒气或规定时间内到达救生仓，然后建图
#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 eb emplace_back
#define maxn 1000006
#define eps 1e-8
#define pi acos(-1.0)
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef unsigned long long ull;
#define MAXN 200005
const int N=;
const int M=;
const int INF=0x3f3f3f3f;
using namespace std;
int n;
struct Edge{
int v,next;
int cap,flow;
}edge[MAXN*];//注意这里要开的够大。。不然WA在这里真的想骂人。。问题是还不报RE。。
int cur[MAXN],pre[MAXN],gap[MAXN],path[MAXN],dep[MAXN];
int cnt=;//实际存储总边数
void isap_init()
{
cnt=;
memset(pre,-,sizeof(pre));
}
void isap_add(int u,int v,int w)//加边
{
edge[cnt].v=v;
edge[cnt].cap=w;
edge[cnt].flow=;
edge[cnt].next=pre[u];
pre[u]=cnt++;
}
void add(int u,int v,int w){
isap_add(u,v,w);
isap_add(v,u,);
}
bool bfs(int s,int t)//其实这个bfs可以融合到下面的迭代里，但是好像是时间要长
{
memset(dep,-,sizeof(dep));
memset(gap,,sizeof(gap));
gap[]=;
dep[t]=;
queue<int>q;
while(!q.empty()) q.pop();
q.push(t);//从汇点开始反向建层次图
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=pre[u];i!=-;i=edge[i].next)
{
int v=edge[i].v;
if(dep[v]==-&&edge[i^].cap>edge[i^].flow)//注意是从汇点反向bfs，但应该判断正向弧的余量
{
dep[v]=dep[u]+;
gap[dep[v]]++;
q.push(v);
// if(v==sp)//感觉这两句优化加了一般没错，但是有的题可能会错，所以还是注释出来，到时候视情况而定
// break;
}
}
}
return dep[s]!=-;
}
int isap(int s,int t)
{
if(!bfs(s,t)) return ;
memcpy(cur,pre,sizeof(pre));
//for(int i=1;i<=n;i++)
//cout<<"cur "<<cur[i]<<endl;
int u=s;
path[u]=-;
int ans=;
while(dep[s]<n)//迭代寻找增广路,n为节点数
{
if(u==t)
{
int f=INF;
for(int i=path[u];i!=-;i=path[edge[i^].v])//修改找到的增广路
f=min(f,edge[i].cap-edge[i].flow);
for(int i=path[u];i!=-;i=path[edge[i^].v])
{
edge[i].flow+=f;
edge[i^].flow-=f;
}
ans+=f;
u=s;
continue;
}
bool flag=false;
int v;
for(int i=cur[u];i!=-;i=edge[i].next)
{
v=edge[i].v;
if(dep[v]+==dep[u]&&edge[i].cap-edge[i].flow)
{
cur[u]=path[v]=i;//当前弧优化
flag=true;
break;
}
}
if(flag)
{
u=v;
continue;
}
int x=n;
if(!(--gap[dep[u]]))return ans;//gap优化
for(int i=pre[u];i!=-;i=edge[i].next)
{
if(edge[i].cap-edge[i].flow&&dep[edge[i].v]<x)
{
x=dep[edge[i].v];
cur[u]=i;//常数优化
}
}
dep[u]=x+;
gap[dep[u]]++;
if(u!=s)//当前点没有增广路则后退一个点
u=edge[path[u]^].v;
}
return ans;
} int t; string people[],cap[];
int book[][];
struct sair{
int x,y,step;
};
int dir[][]={,,,,,-,-,}; void bfs1(int x,int y){
sair s,e;
s.step=,s.x=x,s.y=y;
memset(book,-,sizeof(book));
queue<sair>Q;
Q.push(s);
book[s.x][s.y]=;
while(!Q.empty()){
s=Q.front();
Q.pop();
if(s.step>=t) break;
for(int i=;i<;i++){
e.x=s.x+dir[i][];
e.y=s.y+dir[i][];
if(e.x>=&&e.x<n&&e.y>=&&e.y<n&&book[e.x][e.y]==-&&people[e.x][e.y]!='Y'){
e.step=s.step+;
book[e.x][e.y]=e.step;
Q.push(e);
}
}
}
} void bfs2(int x,int y){
sair s,e;
int tmp[][];
memset(tmp,-,sizeof(tmp));
s.x=x,s.y=y,s.step=;
tmp[s.x][s.y]=;
queue<sair>Q;
Q.push(s);
int w=people[x][y]-'';
add(s.x*n+s.y,s.x*n+s.y+n*n,w);
while(!Q.empty()){
s=Q.front();
Q.pop();
if(s.step>=t) break;
for(int i=;i<;i++){
e.x=s.x+dir[i][];
e.y=s.y+dir[i][];
if(e.x<||e.x>=n||e.y<||e.y>=n||people[e.x][e.y]=='Z'||people[e.x][e.y]=='Y') continue;
if(tmp[e.x][e.y]==-&&(book[e.x][e.y]==-||book[e.x][e.y]>=s.step+)){
if(book[e.x][e.y]==s.step+){
if(cap[e.x][e.y]>=''&&cap[e.x][e.y]<=''){
add(x*n+y,e.x*n+e.y+n*n,w);
}
}
else{
e.step=s.step+;
tmp[e.x][e.y]=e.step;
add(x*n+y,e.x*n+e.y+n*n,w);
Q.push(e);
}
}
}
}
} int main(){
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
cin>>n>>t;
int sx,sy;
isap_init();
for(int i=;i<n;i++){
cin>>people[i];
for(int j=;j<n;j++){
if(people[i][j]=='Z'){
sx=i,sy=j;
}
}
}
for(int i=;i<n;i++) cin>>cap[i];
bfs1(sx,sy);
for(int i=;i<n;i++){
for(int j=;j<n;j++){
if(people[i][j]>=''&&people[i][j]<=''){
bfs2(i,j);
}
}
}
int S=n*n*;
int T=n*n*+;
for(int i=;i<n;i++){
for(int j=;j<n;j++){
if(people[i][j]>=''&&people[i][j]<=''){
add(S,i*n+j,people[i][j]-'');
}
if(cap[i][j]>=''&&cap[i][j]<=''){
add(i*n+j+n*n,T,cap[i][j]-'');
}
}
}
n=n*n*+;
int ans=isap(S,T);
cout<<ans<<endl;
}