rank:217/883
我们（kugwzk）好菜啊....怎么又被学弟们打爆了啊。。。学弟们都嚷嚷着要去区域赛了啊。。。
1001
线段树合并，预先处理出每个值在最终的序列中的位置，维护一个前缀和的和的标记，然后在dfs的过程中线段树合并。时间复杂度为O(nlogn)，空间复杂度就大了一点，补题的时候卡了半天的内存。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#define maxn 100002
#define inf 0x3f3f3f3f
#define REP(i,x,y) for(int i=x;i<(y);i++)
#define RREP(i,x,y) for(int i=x;i>(y);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int n,a[maxn],root[maxn],tot;
pii aa[maxn];
vector<int>e[maxn];
int ls[maxn*18],rs[maxn*18],Size[maxn*18];
ll sum1[maxn*18],sum2[maxn*18];
void build(int& rt,int pos,int l,int r) {
if(!rt) rt=++tot;
Size[rt]=1;
sum1[rt]=sum2[rt]=aa[pos].first;
if(l==r) return ;
int m=((l+r)>>1);
if(pos<=m) build(ls[rt],pos,l,m);
else build(rs[rt],pos,m+1,r);
}
int Merge(int x,int y) {
if(!x||!y) return x+y;
ls[x]=Merge(ls[x],ls[y]);
rs[x]=Merge(rs[x],rs[y]);
Size[x]=Size[ls[x]]+Size[rs[x]];
sum1[x]=sum1[ls[x]]+sum1[rs[x]];
sum2[x]=sum2[ls[x]]+1LL*Size[rs[x]]*sum1[ls[x]]+sum2[rs[x]];
return x;
}
void dfs(int rt,int fa) {
build(root[rt],a[rt],1,n);
REP(i,0,e[rt].size()) {
if(e[rt][i]==fa) continue;
dfs(e[rt][i],rt);
Merge(root[rt],root[e[rt][i]]);
}
}
int main()
{
int T;scanf("%d",&T);
while(T--) {
scanf("%d",&n);
tot=0;
REP(i,1,n+1) {
root[i]=0;
e[i].clear();
}
REP(i,1,n+1) {
scanf("%d",&a[i]);
aa[i]=make_pair(a[i],i);
}
sort(aa+1,aa+1+n);
REP(i,1,n+1) a[i]=lower_bound(aa+1,aa+1+n,make_pair(a[i],i))-aa;
REP(i,1,n) {
int u,v;scanf("%d %d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1,0);
for(int i=1;i<=n;i++) {
printf("%I64d ",sum2[root[i]]);
}
puts("");
for(int i=1;i<=tot;i++) Size[i]=ls[i]=rs[i]=sum1[i]=sum2[i]=0;
}
}
1002
李大爷比赛的时候貌似写错了一些地方，赛后补过了。
#include <bits/stdc++.h>
const int mod = 1e9+7;
const double ex = 1e-10;
#define inf 0x3f3f3f3f
using namespace std;
int sum[3000006];
int val[3000006];
int not_prime[2000050],prime[2000050],mu[2000050],tot;
void getmu(int n){
not_prime[0]=not_prime[1]=1;
mu[1]=1;
for (int i = 2; i<=n; i++){
if(!not_prime[i]){
mu[i]=-1;
prime[++tot]=i;
}
for(int j=1;j<=tot&&prime[j]*i<=n;j++){
not_prime[prime[j]*i]=1;
if(i%prime[j]==0){
mu[prime[j]*i]=0;
break;
}
mu[prime[j]*i]=-mu[i];
}
}
}
void init()
{
for (int i = 1;i<=1000000;i++)
{
sum[i] = (sum[i] + 1) % mod;
sum[i+1] = (sum[i+1] - 1+mod) % mod;
int cnt = 2;
for (int j = i+1; j<=1000000 ;j+=i)
{
sum[j]=(sum[j] + cnt) % mod;
sum[j+i]=(sum[j+i] - cnt + mod) % mod;
cnt++;
}
}
for (int i = 1;i<=1000000 ;i++)
sum[i] = val[i] = (sum[i] + sum[i-1]) % mod;
for (int i = 2; i<=1000000;i++)
{
if (mu[i]==0) continue;
for (int j = i; j<=1000000 ;j+=i)
sum[j] = ( sum[j] + mu[i]*val[j/i] + mod ) % mod;
}
for (int i = 1;i<=1000000 ;i++)
sum[i] = (sum[i] + sum[i-1]) % mod;
}
int main()
{
int N;
getmu(1000000);
init();
while (scanf("%d",&N) == 1)
{
printf("%d
",(sum[N])%mod);
}
return 0;
}
1008
直接暴力bitset加剪枝。正解则是通过限制2推出了一些性质。
#include <bits/stdc++.h>
using namespace std;
const int maxn=1005;
int n,K;
bitset<2000010> bit;
int T,a[maxn],mmax,mmin;
char op[maxn][2];
int main()
{
scanf("%d",&T);
while (T--) {
scanf("%d%d",&n,&K);
mmax=0,mmin=0;
for (int i=0;i<n;++i)
scanf("%d",&a[i]);
for (int i=0;i<n;++i)
scanf("%s",op[i]);
mmax=mmin=0;
for (int i=0;i<n;++i) {
if (op[i][0]=='L') {
mmax+=a[i];
}
if (op[i][0]=='D') {
mmin-=a[i];
}
if (op[i][0]=='N') {
mmax+=a[i];
mmin-=a[i];
}
}
if (K>mmax||K<mmin) {
puts("no");
continue;
}
bit.reset();
bit[1000005]=1;
int flag=0;
for (int i=0;i<n;++i) {
if (op[i][0]=='N') {
bit=bit|(bit>>a[i]);
bit=bit|(bit<<a[i]);
} else if (op[i][0]=='L')
bit=bit|(bit<<a[i]);
else if (op[i][0]=='D')
bit=bit|(bit>>a[i]);
if (bit[1000005+K]==1) {
flag=1;
break;
}
}
if (flag)
puts("yes");
else
puts("no");
}
return 0;
}
1009
容斥一下。
#include <bits/stdc++.h>
using namespace std;
const int maxn=2005;
const long long mod=1e9+7;
long long C[maxn][maxn],Pow[maxn];
int T;
long long n,m;
inline long long ksm(long long x,long long n) {
long long ret=1;
while (n>0) {
if (n&1)
ret=ret*x%mod;
n>>=1;
x=x*x%mod;
}
return ret;
}
inline long long solve(long long a,long long b,long long n) {
long long coe=1,now=0;
for (int i=a;i>=1;--i) {
now=(now+coe*C[a][i]*Pow[i]%mod+mod)%mod;
coe=-coe;
}
now=now*C[m][b]%mod*Pow[b]%mod;
return now;
}
int main()
{
for (int i=0;i<maxn;++i) {
C[i][0]=C[i][i]=1;
for (int j=1;j<i;++j)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
/*
for (int i=0;i<6;++i)
for (int j=0;j<=i;++j)
printf("%I64d%c",C[i][j],j==i?'
':' ');
*/
scanf("%d",&T);
while (T--) {
scanf("%I64d%I64d",&n,&m);
for (int i=1;i<=m;++i)
Pow[i]=ksm(i,n);
long long res=0;
for (int i=1;i<=m-1;++i)
res=(res+solve(i,m-i,n))%mod;
printf("%I64d
",res);
}
return 0;
}