Codeforces Beta Round #72 (Div. 2 Only)
http://codeforces.com/contest/84
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;
int main(){
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
ll n;
cin>>n;
cout<<*n-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 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; int n;
ll a[]; int main(){
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
cin>>n;
for(int i=;i<=n;i++) cin>>a[i];
ll ans=n;
ll co=;
for(int i=;i<n;i++){
if(a[i]==a[i+]){
co++;
}
else{
ans+=co*(co-)/;
co=;
}
}
ans+=co*(co-)/;
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 unsigned long long ull; const int N = , D = ;
int n, m, x, y, c[N], r[N], s[N];
vector<int> v[D * + ]; int main(){
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
cin>>n;
int ans=;
for (int i = ; i <= n; i++){
cin>>c[i]>>r[i];
c[i] += D; s[i] = -;
for (int j = c[i] - r[i]; j <= c[i] + r[i]; j++) v[j].push_back(i);
}
cin>>m;
for (int i = ; i <= m; i++){
cin>>x>>y;
x += D;
for (auto j : v[x]) if (s[j] == -)
if (y * y + (x - c[j]) * (x - c[j]) <= r[j] * r[j]){
s[j] = i;
ans++;
}
}
cout<<ans<<endl;
for (int i = ; i <= n; i++) cout<<s[i]<<" ";
}
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; ll a[];
ll n,k;
int book[];
vector<int>ans; bool erfen(ll mid){
ll sum=;
for(int i=;i<=n;i++){
sum+=min(a[i],mid);
}
if(sum>=k) return true;
return false;
} int main(){
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
cin>>n>>k;
ll sum=;
ll Max=;
ll L,R,mid;
for(int i=;i<=n;i++){
cin>>a[i];
sum+=a[i];
Max=max(Max,a[i]);
}
if(sum<k) cout<<-<<endl;
else if(sum==k){}
else{
L=,R=Max,mid;
while(L<=R){
mid=L+R>>;
if(erfen(mid)){
R=mid-;
}
else{
L=mid+;
}
}
ll kk=R;
sum=;
for(int i=;i<=n;i++){
sum+=min(a[i],kk);
a[i]-=min(a[i],kk);
}
int flag=;
for(int i=;i<=n;i++){
if(sum>k&&a[i]>){
book[i]=;
ans.pb(i);
}
else if(a[i]>){
sum++;
a[i]--;
if(sum>k&&flag&&a[i]>=){
flag=;
ans.pb(i);
book[i]=;
}
} }
for(int i=;i<=n;i++){
if(!book[i]&&a[i]>){
book[i]=;
ans.pb(i);
}
}
for(int i=;i<ans.size();i++){
cout<<ans[i]<<" ";
}
} }
E
__builtin_popcount() 函数，计算一个数转二进制之后有几个1
一道很好的最短路的题目。
题意：求S到T的最短路径，其中，路径上不同的字母不能超过K个，且答案的字典序要最小，不存在输出-1
思路：因为K小于等于4,所以可以用状压来存放不同字母的个数。在优先队列中存放距离，路径的字符串，K和该点的下表，跑一次最短路即可。
#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<pair<int,string>,pii> ppp;
typedef unsigned long long ull; int n,m,k;
int S,T;
string s[];
set<pii>se; int dist(int a,int b){
return abs(a/m-b/m)+abs(a%m-b%m);
} int dir[][]={,,,,,-,-,}; void Dijstra(){
priority_queue<ppp,vector<ppp>,greater<ppp>>Q;
Q.push({{dist(S,T),""},{,S}});
ppp ss;
string str;
int book,pos;
int x,y,xx,yy;
while(!Q.empty()){
ss=Q.top();
Q.pop();
str=ss.first.second;
book=ss.second.first;
pos=ss.second.second;
if(!se.count({book,pos})){
se.insert({book,pos});
x=pos/m,y=pos%m;
for(int i=;i<;i++){
xx=x+dir[i][];
yy=y+dir[i][];
if(xx>=&&xx<n&&yy>=&&yy<m){
if(s[xx][yy]=='T'){
cout<<str<<endl;
exit();
}
if(__builtin_popcount(book|(<<(s[xx][yy]-'a')))<=k)
Q.push({{dist(xx*m+yy,T)+str.length()+,str+s[xx][yy]},{book|(<<(s[xx][yy]-'a')),xx*m+yy}});
}
}
}
} } int main(){
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
#endif
std::ios::sync_with_stdio(false);
cin>>n>>m>>k;
for(int i=;i<n;i++){
cin>>s[i];
for(int j=;j<m;j++){
if(s[i][j]=='S'){
S=i*m+j;
}
if(s[i][j]=='T'){
T=i*m+j;
}
}
}
Dijstra();
cout<<-<<endl;
}