https://ac.nowcoder.com/acm/contest/272/A
v<=k时 答案就是k个1
否则贪心的从中间向两边添加1
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define pb push_back
#define mp make_pair
const LL mod=1e9+;
int s[];
int main(){
int v,k,i,j;
while(cin>>v>>k){
s[]=;
s[v-]=;
for(i=(v-)/,j=;j*+<=k;i--,j++){
s[i]=;
s[v--i]=;
}
if(v<k){
for(i=v;i<k;++i) s[i]=;
v=k;
}
LL ans=;
for(i=;i<v;++i){
ans=(ans*+s[i])%mod;
}
cout<<ans<<endl;
}
return ;
}
https://ac.nowcoder.com/acm/contest/272/B
考虑每一个点做出的贡献，通过这个点的路径数量是奇数就贡献一个A[u]，否则就是0。
求每个点的路径数量时，只要dfs出所有子树的节点数量即可。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define pb push_back
#define mp make_pair
const LL mod=1e9+;
const int maxn=;
vector<int>g[maxn];
LL A[maxn],n,ans=;
int dfs(int u,int fa){
int sum=,s=;
for(int i=;i<g[u].size();++i){
int v=g[u][i];
if(v==fa) continue;
int tmp=dfs(v,u);
//s+=tmp;
sum+=(tmp*(s+));
s+=tmp;
//if(u==1)cout<<"sum= "<<sum<<" "<<s<<endl;
sum%=;
}
sum+=((LL)n-s-)*((LL)s+);
sum%=;
s++;
if(sum)ans^=A[u];
return s;
}
int main(){
int i,j,u,v;
scanf("%lld",&n);
for(i=;i<n;++i){
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
for(i=;i<=n;++i)scanf("%lld",A+i);
dfs(,);
printf("%lld\n",ans);
return ;
}
https://ac.nowcoder.com/acm/contest/272/C
观察发现n次操作之后白球个数的概率都是1/(n+1), 所以答案就是 1/(1+n) *(n+2)*(n+1)/2 = (n+2)/2
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
scanf("%d",&n);
printf("%.7f\n",(2.0+n)/);
return ;
}