http://codeforces.com/contest/462
要求是否全部的字符都挨着偶数个'o'
#include <cstdio>
using namespace std;
char maz[][];
int n;
int cnt[][];
const int dx[]={,,-,};
const int dy[]={,-,,};
int main(){
scanf("%d",&n);
gets(maz[]);
for(int i=;i<n;i++){
gets(maz[i]);
}
for(int i=;i<n;i++){
for(int j=;j<n;j++){
if(maz[i][j]=='o'){
for(int k=;k<;k++){
int nx=i+dx[k];
int ny=j+dy[k];
if(nx<n&&ny<n&&nx>=&&ny>=){cnt[nx][ny]++;}
}
}
}
}
for(int i=;i<n;i++){
for(int j=;j<n;j++){
if(cnt[i][j]&){puts("NO");return ;}
}
}
puts("YES");
return ;
}
贪心
#include <cstdio>
#include <algorithm>
using namespace std;
long long n,k;
long long cnt[];
char maz[];
int main(){
scanf("%I64d%I64d",&n,&k);
gets(maz);
gets(maz);
for(int i=;i<n;i++)cnt[maz[i]-'A']++;
sort(cnt,cnt+);
long long ans=;
for(int i=;i>=;i--){
if(cnt[i]>=k){
ans+=k*k;
k=;
}
else {
k-=cnt[i];
ans+=cnt[i]*cnt[i];
}
if(k==)break;
}
printf("%I64d\n",ans);
return ;
}
题解意思:
这是一道霍夫曼编码的反问题,把所有边权取反就是霍夫曼树问题,详细证明请看算法导论,大概证明一下:
可以把每次的拿来拆分的每一段的都作为树上的节点,长度为1的值必然是叶节点,会在统计一次后被抛出,这时父节点权值则是子节点权值之和,而且必然是一颗二叉树,这与题目是符合的,也就是说深度越大的叶节点加和的次数越多,那么把最大的那两个节点先放在树里,那么它们的父节点就拥有两个节点之和的性质,那么再添加次大的,如此构建就形成了整棵最优树,(算法导论可以严格证明这是棵最优树,通过反证法),于是除了最大的两个点加了n次,其余的点分别加了n-1,n-2,....2次
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=;
int n;
long long a[maxn];
int main(){
scanf("%d",&n);
long long ans=,sum=;
for(int i=;i<n;i++){scanf("%I64d",a+i);sum+=a[i];}
sort(a,a+n);
ans=sum;
for(int i=;i<n;i++){
ans+=sum;
sum-=a[i-];
}
printf("%I64d\n",ans);
return ;
}
D:Appleman and Tree
树形dp
这是一道树形dp,我一开始想到奇怪的地方去了,什么连通域之类的
对每个点,dp记录使其的所有子树成为单黑或纯白的方式,最后再加上自身的黑/白属性
具体来说
初始化:子树单黑=0,子树纯白=1
单黑=现有单黑*子树纯白+子树单黑*现有纯白
纯白=现有纯白*子树纯白
然后加入自身的属性
如果自身为黑,那么单黑=子树纯白(现有黑:切掉所有子节点成为0)
如果自身为白,那么纯白*=子树纯白(切掉本身使得孤立的方式更多)
#include<cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=;
const long long mod= ;
long long dp[maxn][];
int color[maxn];
vector<int> G[maxn];
bool vis[maxn];
void dfs(int s){
dp[s][]=;
dp[s][]=;
vis[s]=true;
for(int i=;i<G[s].size();i++){
int t=G[s][i];
if(vis[t])continue;
dfs(t);
dp[s][]=(dp[s][]*dp[t][]+dp[s][]*dp[t][])%mod;
dp[s][]=dp[s][]*dp[t][]%mod;
}
if(color[s]==){
dp[s][]=dp[s][];
}
else dp[s][]+=dp[s][];
dp[s][]%=mod;
dp[s][]%=mod;
}
int main(){
int n;
scanf("%d",&n);
for(int i=;i<n;i++){
int temp;
scanf("%d",&temp);
G[temp].push_back(i);
}
for(int i=;i<n;i++)scanf("%d",color+i);
dfs();
printf("%I64d\n",dp[][]);
return ;
}
E:Appleman and a Sheet of Paper
线段树
翻折,当长度>len/2的时候那么就反向翻折,这时候相当于反向了一次,需要反着来统计
看上去思路很清晰但是很麻烦
#include<cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=;
const int maxnode=;
long long w[maxnode];
int cur,s,e,len,n,q;
int num(int i){//返回正确的标号,传入的是从开始的端点所需经过距离
if(cur==){return s+i;}
return e-i;
}
void update(int k,int d){//更新线段树
int tk=k;
k+=n-;
w[k]+=d;
while(k>){
k=(k-)/;
w[k]+=d;
}
}
void inv(int l){//翻转
int tl;
if(l*>len){tl=len-l;cur^=;}//翻转统计的同时就要反向更新了
else tl=l;
for(int i=;i<tl;i++){
int td=num(tl*--i);
int td2=num(i);
update(td,w[td2+n-]);
update(td2,-w[td2+n-]);
}
if(cur)e-=tl;else s+=tl;
len=e-s+;
}
long long query(int a,int b,int k,int l,int r){
if(r<=a||l>=b||l>=r)return ;
if(a<=l&&r<=b){
return w[k];
}
else {
long long v1=query(a,b,k*+,l,(l+r)/);
long long v2=query(a,b,k*+,(l+r)/,r);
return v1+v2;
}
}
int main(){
scanf("%d%d",&n,&q);int tn=n,ttn=n;n=;
while(tn>){n<<=;tn>>=;}
for(int i=;i<ttn;i++)update(i,);
s=;e=ttn-;len=ttn;
while(q--){
int op;
scanf("%d",&op);
if(op==){
int l;
scanf("%d",&l);
inv(l);
}
else{
int l,r;
scanf("%d%d",&l,&r);
if(cur){
l=num(l-);//这里卡我半天因为题目给的是从s开始的序号所以从e开始就要+1,传进的参数要-1
r=num(r-);
}
else {
l=num(l);
r=num(r);
}
if(l>r)swap(l,r);
long long ans=query(l,r,,,n);
printf("%I64d\n",ans);
} }
}