Codeforces Beta Round #27 (Codeforces format, Div. 2)
http://codeforces.com/contest/27
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 maxn 1000005
typedef long long ll;
typedef unsigned long long ull;
const ull MOD=;
/*#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];
}
sort(a+,a+n+);
int i;
for(i=;i<=n;i++){
if(a[i]!=i){
cout<<i<<endl;
break;
}
}
if(i==n+) cout<<n+<<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 maxn 1000005
typedef long long ll;
typedef unsigned long long ull;
const ull MOD=;
/*#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif */ int book[][];
int n;
int d[]; void Check(int &x,int &y){
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
if(i==j) continue;
if(!book[i][j]){
x=i,y=j;
return;
}
}
}
} int main(){
#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
cin>>n;
int nn=n*(n-)/-;
int u,v;
for(int i=;i<=nn;i++){
cin>>u>>v;
book[u][v]=book[v][u]=;
d[u]++;
}
int x,y;
Check(x,y);
if(d[x]>d[y]){
cout<<x<<" "<<y<<endl;
}
else{
cout<<y<<" "<<x<<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 maxn 1000005
typedef long long ll;
typedef unsigned long long ull;
const ull MOD=;
/*#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif */ int a[];
int n; int Check(){
int flag=;
for(int i=;i<n;i++){///<<<<<<
if(a[i]>a[i+1]){
flag=;
}
}
if(flag==){
return ;
}
flag=;
for(int i=;i<n;i++){///>>>>>>
if(a[i]<a[i+]){
flag=;
}
}
if(flag==) return ;
return -;
} struct sair{
int v,pos;
}b[];
int main(){
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
cin>>n;
int co=;
for(int i=;i<=n;i++){
cin>>a[i];
if(a[i]!=a[i-]){
b[co].v=a[i];
b[co].pos=i;
co++;
}
}
co--;
int flag=Check();
if(flag==||flag==){
cout<<<<endl;
}
else{
cout<<<<endl; for(int i=;i<co;i++){
if(b[i-].v>b[i].v&&b[i].v<b[i+].v){
cout<<b[i-].pos<<" "<<b[i].pos<<" "<<b[i+].pos<<endl;
break;
}
if(b[i-].v<b[i].v&&b[i].v>b[i+].v){
cout<<b[i-].pos<<" "<<b[i].pos<<" "<<b[i+].pos<<endl;
break;
}
}
}
}
D
用类似二分染色的思想，把交叉的道路染成不同的颜色，如果判断的时候出现交叉的道路有相同的颜色，就输出Impossible
#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;
const ull MOD=;
/*#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif */ vector<int>ve[];
int n,m;
int s[],t[];
int vis[];
int col[]; void dfs(int pos,int c){
if(vis[pos]) return;
vis[pos]=;
col[pos]=c;
for(int i=;i<ve[pos].size();i++){
dfs(ve[pos][i],c^);
if(col[pos]==col[ve[pos][i]]){
cout<<"Impossible"<<endl;
exit();
}
}
} int main(){
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=;i<=m;i++){
cin>>s[i]>>t[i];
if(s[i]>t[i]) swap(s[i],t[i]);
}
for(int i=;i<=m;i++){
for(int j=;j<=m;j++){
if(s[i]<s[j]&&t[i]<t[j]&&s[j]<t[i]){
ve[i].pb(j);
ve[j].pb(i);
}
}
}
for(int i=;i<=m;i++){
dfs(i,);
}
for(int i=;i<=m;i++){
if(col[i]) cout<<'i';
else cout<<'o';
}
}
E
知识点：反素数
参考博客：https://www.cnblogs.com/handsomecui/p/5017484.html
#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 maxn 1000005
typedef long long ll;
typedef unsigned long long ull;
const ull MOD=;
/*#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif */ int prim[]={,,,,,,,,,,,,,,,};
int n;
ull ans=-; void dfs(int pos,ull v,int num){
if(num==n&&ans>v) ans=v;
for(int i=;i<=;i++){
if(num*(i+)>n||v*prim[pos]>ans) break;
v*=prim[pos];
dfs(pos+,v,num*(i+));
}
} int main(){
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
cin>>n;
dfs(,,);
cout<<ans<<endl;
}
