Codeforces Beta Round #75 (Div. 2 Only)
http://codeforces.com/contest/92
A
#include<iostream>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define maxn 100005
typedef long long ll;
typedef unsigned long long ull;
const ull MOD=;
/*#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif */ int main(){
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
int n,m;
cin>>n>>m;
int i=;
while(i+<=m){
m-=i+;
i++;
if(i==n) i%=n;
}
cout<<m<<endl;
}
B
模拟+找规律
#include<iostream>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define sqr(x) ((x)*(x))
#define maxn 100005
typedef long long ll;
typedef unsigned long long ull;
const ull MOD=;
/*#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif */ /// int main(){
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
string str;
cin>>str;
if(str==""){
cout<<;
return ;
}
int ans=;
for(int i=str.length()-;i>=;i--){
if(str[i]==''&&i==) break;
if(str[i]==''){
ans+=;
int l=i;
while(l>=&&str[l]==''){
str[l]='';
l--;
}
if(l>=) str[l]='';
}
else{
ans++;
} }
cout<<ans<<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 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 pair<int,int> pii;
typedef pair<char,int> pci;
typedef pair<pair<int,string>,pii> ppp;
typedef unsigned long long ull;
/*#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif */ vector<int>ve[];
int book[]; int main(){
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
string s1,s2;
cin>>s1>>s2;
int ans=;
for(int i=;i<s1.length();i++){
ve[s1[i]-'a'].pb(i);
}
int pos=-;
int x,tmp;
for(int i=;i<s2.length();i++){
x=s2[i]-'a';
if(ve[x].size()==){
cout<<-<<endl;
return ;
}
tmp=lower_bound(ve[x].begin(),ve[x].end(),pos+)-ve[x].begin();
if(tmp!=ve[x].size()){
pos=ve[x][tmp];
}
else{
ans++;
pos=lower_bound(ve[x].begin(),ve[x].end(),)-ve[x].begin();
pos=ve[x][pos];
}
// cout<<tmp<<" "<<pos<<" "<<ans<<endl;
// cout<<pos<<endl;
}
cout<<ans<<endl;
}
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 100005
#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 pair<int,int> pii;
typedef pair<char,int> pci;
typedef pair<pair<int,string>,pii> ppp;
typedef unsigned long long ull;
/*#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif */ int a[maxn];
int tree[maxn<<];
int n; void push_up(int rt){
tree[rt]=min(tree[rt<<],tree[rt<<|]);
} void build(int l,int r,int rt){
if(l==r){
tree[rt]=a[l];
return;
}
int mid=l+r>>;
build(lson);
build(rson);
push_up(rt);
} int query(int L,int R,int v,int l,int r,int rt){
if(l==r&&L<=l&&R>=r){
return l;
}
int mid=l+r>>;
if(L<=mid&&tree[rt<<]<v){
return query(L,R,v,lson);
}
else if(R>mid&&tree[rt<<|]<v){
return query(L,R,v,rson);
}
return -;
} int main(){
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
cin>>n;
for(int i=n;i>=;i--) cin>>a[i];
build(,n,);
int pos;
vector<int>ans;
for(int i=;i<=n;i++){
pos=query(,i,a[i],,n,);
if(pos==-) ans.pb(pos);
else ans.pb(i-pos-);
}
reverse(ans.begin(),ans.end());
for(int i=;i<ans.size();i++) cout<<ans[i]<<" ";
}
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 100005
#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 pair<int,int> pii;
typedef pair<char,int> pci;
typedef pair<pair<int,string>,pii> ppp;
typedef unsigned long long ull;
const long long MOD=1e9+;
/*#ifndef ONLINE_JUDGE
freopen("1.txt","r",stdin);
#endif */ int n,m;
int fa[]; int Find(int x){
int r=x,y;
while(x!=fa[x]) x=fa[x];
while(r!=x){
y=fa[r];
fa[r]=x;
r=y;
}
return x;
} int main(){
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
cin>>n>>m;
int x,y,xx,yy;
ll ans=;
for(int i=;i<=n;i++) fa[i]=i;
for(int i=;i<m;i++){
cin>>x>>y;
xx=Find(x),yy=Find(y);
if(xx==yy){
ans=(ans+ans)%MOD;
}
else fa[xx]=yy;
cout<<ans-<<endl;
} }