1001 没有兄弟的舞会
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 100005; int t,n; int a[maxn],fa[maxn]; struct node { int to,w; node(){} node(int _to,int _w) { to=_to;w=_w; } bool operator < (const node & _node) { return w <_node.w; } }; vector<node> M[maxn]; int main() { int t;scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=1;i<=n;i++)M[i].clear(); for(int i=2;i<=n;i++) { scanf("%d",&fa[i]); } for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int i=2;i<=n;i++) { M[fa[i]].push_back(node(i,a[i])); } for(int i=1;i<=n;i++) { sort(M[i].begin(),M[i].end()); } long long ans1=0,ans2=0; long long sum=0,sum1=0; for(int i=1;i<=n;i++) { if(M[i].size()==0)continue; else if(M[i].size()==1) { ans1 += max((ll)0,(ll)M[i][0].w); ans2 += min((ll)0,(ll)M[i][0].w); } else{ int len = M[i].size(); ans1 += max((ll)0,(ll)M[i][len-1].w); ans2 += min((ll)0,(ll)M[i][0].w); sum = max(sum,(ll)M[i][len-2].w); sum1 = min(sum1,(ll)M[i][1].w); } // cout<<ans1<<" "<<ans2<<endl; } if(a[1]<0)ans2+=a[1]; else ans1+=a[1]; cout<<ans1+sum<<" "<<ans2+sum1<<endl; } return 0; }
1002 序列期望
#include <bits/stdc++.h> using namespace std; int l[105],r[105]; int mx,mi; long long mod = 1e9 + 7; long long ans = 0; long long cnt; long long power(long long a,long long k){ long long ret = 1; a = a % mod; while(k){ if(k & 1) ret = ret * a % mod; a = a * a % mod; k >>= 1; } return ret; } long long calc(long long beg,long long end){ if(beg > end) return 0; long long ret = (beg+end)*(end-beg+1)/2; return ret; } int main() { int T; scanf("%d",&T); while(T--){ int n; scanf("%d",&n); mx = 0,mi = 0; ans = 0; long long tot = 1; for(int i = 1;i <= n;++i){ scanf("%d%d",&l[i],&r[i]); mx = max(mx,r[i]); mi = max(l[i],mi); tot = tot * (r[i]-l[i]+1) % mod; } long long up,tmp,tmp2,up2; for(int i = mi;i <= mx;++i){ tmp = 1; tmp2 = 1; for(int j = 1;j <= n;++j){ up = min(r[j],i); up2 = min(i-1,r[j]); tmp2 = tmp2 * calc(i-up2+1,i-l[j]+1) % mod; tmp = tmp * calc(i-up+1,i-l[j]+1) % mod; } ans = ans + tmp - tmp2 + mod; ans %= mod; } ans = ans * power(tot,mod-2)%mod; printf("%I64d ",ans); } return 0; }
1003 带劲的and和
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 100005; const int mod = 1e9+7; int n,m; int t; int v[maxn]; ll ans = 0; int par[maxn]; ll poww[35]; int ta[maxn][35],tb[maxn][35]; struct number { int x,id; bool operator < (const number & _number) { if(id == _number.id) { return x < _number.x; } return id < _number.id; } }tu[maxn]; void init(int n) { for (int i = 0; i <= n; i++) { par[i] = i; } } int fin(int x) { if (par[x] == x) { return x; } else { return par[x] = fin(par[x]); } } void unite(int x, int y) { x = fin(x); y = fin(y); if (x == y) return; par[x] = y; } bool same(int x, int y) { return fin(x) == fin(y); } void bi(int pos,int num) { int i=0; while(num) { ta[pos][i]=(num%2);i++; num/=2; } } ll ask(int l,int r) { for(int i=l;i<=r;i++) { bi(i,tu[i].x); } for(int i=0;i<=31;i++) { tb[l][i]=ta[l][i]; } for(int i=l+1;i<=r;i++) { for(int j=0;j<=31;j++) { tb[i][j] = tb[i-1][j] + ta[i][j]; } } ll ret = 0; for(int i=l+1;i<=r;i++) { for(int j=0;j<=31;j++) { if(ta[i][j]) ret = (ret + (ll)(tu[i].x*poww[j])%mod*tb[i-1][j])%mod; } } ret%=mod; return ret; } int main() { poww[0]=1; for(int i=1;i<=31;i++) { poww[i]=poww[i-1]*2; } scanf("%d",&t); while(t--) { ans = 0; scanf("%d%d",&n,&m); init(n); for(int i=1;i<=n;i++)scanf("%d",&v[i]); for(int i=1;i<=m;i++) { int u,uu; scanf("%d%d",&u,&uu); unite(u,uu); } for(int i=1;i<=n;i++) { tu[i].id=fin(i); tu[i].x=v[i]; } sort(tu+1,tu+n+1); int l=1,r=1; memset(ta,0,sizeof(ta)); for(int i=2;i<=n;i++) { if(tu[i].id == tu[i-1].id)r++; else { ans = (ans+ask(l,r))%mod; l = r = i; } //cout<<ans<<endl; } // cout<<l<<" fjsdkfldk "<<r<<endl; ans = (ans+ask(l,r))%mod; cout<<ans<<endl; } }