像我这种菜鸡只能打Div2QAQ……这里放一下除了Challenge之外的题解。
最优解只能是正负分两半。
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100000;
int te,n,A,B;
int main(){
freopen("CHNUM.in","r",stdin);freopen("CHNUM.out","w",stdout);
for (scanf("%d",&te);te;te--){
scanf("%d",&n);A=B=0;for (int i=1,x;i<=n;i++) scanf("%d",&x),x>0?A++:B++;
if (A<B) swap(A,B);B?printf("%d %d\n",A,B):printf("%d %d\n",A,A);
}return 0;
}
一旦存在一位 $i$ 使得 $a_i>a_{i+1}$ 或者 $a_i>d(i=n)$ ,就肯定会把 $a_i$ 删掉,所以不停地换就行了。
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxl=20;
int te,D,a[maxl+5];LL n;
inline int Find() {for (int i=1;i<=a[0];i++) if (a[i]>a[i+1]) return i;return -1;}
int main(){
freopen("CHDIGER.in","r",stdin);freopen("CHDIGER.out","w",stdout);
for (scanf("%d",&te);te;te--){
scanf("%lld%d",&n,&D);a[0]=0;do a[++a[0]]=n%10,n/=10; while (n);reverse(a+1,a+1+a[0]);a[a[0]+1]=D;
for (int pos=Find();~pos;pos=Find()) {for (int i=pos;i<a[0];i++) a[i]=a[i+1];a[a[0]]=D;}
for (int i=1;i<=a[0];i++) putchar(a[i]+48);puts("");
}return 0;
}
直接每次 $O(2^5)$ 维护。
#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;
const int maxn=100000,maxs=1<<5;
int te,n,ID[256],num[maxs];LL ans;
inline char getlow() {char ch=getchar();while (!islower(ch)) ch=getchar();return ch;}
int main(){
freopen("JAIN.in","r",stdin);freopen("JAIN.out","w",stdout);
ID['a']=0;ID['e']=1;ID['i']=2;ID['o']=3;ID['u']=4;
for (scanf("%d",&te);te;te--){
scanf("%d",&n);for (int i=0;i<maxs;i++) num[i]=0;ans=0;
for (int i=1;i<=n;i++){
int S=0;for (char ch=getlow();islower(ch);ch=getchar()) S|=1<<ID[ch];
ans+=num[S^maxs-1];for (int s=S;s;s=s-1&S) num[s]++;num[0]++;
}printf("%lld\n",ans);
}return 0;
}
枚举左端点 $L$ ,然后从左往右推 $R$ ,按照题意模拟就行了……
本来以为这道题会卡常的……就学了一下树状数组求第 $k$ 大,结果线段树随便过……
树状数组求第 $k$ 大:从高位到低位检查,假设当前答案为 $ans$ ,那么第 $i$ 位加上去之后会多出 $(ans,ans+2^i]$ 这一块,即 $c[ans+2^i]$ ,检查加上去会不会大于等于 $k$ ,如果大于等于说明不能加这一位。
代码超级短,但是不能处理值域很大的情况。
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=2000,maxa=2000,Log=10;
int te,n,m,K,a[maxn+5],MAX,c[maxa+5],ans;
inline void Update(int x,int tem) {for (int i=x;i<=MAX;i+=i&-i) c[i]+=tem;}
inline int Sum(int x) {int sum=0;for (int i=x;i>0;i-=i&-i) sum+=c[i];return sum;}
inline int getkth(int k,int ans=0,int cnt=0){
for (int i=Log;~i;i--) (ans^=1<<i)>MAX||cnt+c[ans]*m>=k?ans^=1<<i:cnt+=c[ans]*m;return ans+1;
}
int main(){
freopen("SUBPRNJL.in","r",stdin);freopen("SUBPRNJL.out","w",stdout);
for (scanf("%d",&te);te;ans=0,te--){
scanf("%d%d",&n,&K);for (int i=1;i<=n;i++) scanf("%d",&a[i]),MAX=max(MAX,a[i]);
for (int l=1;l<=n;l++){
for (int i=1;i<=MAX;i++) c[i]=0;
for (int r=l;r<=n;r++){
m=(K+r-l)/(r-l+1);Update(a[r],1);int now=getkth(K),cnt=Sum(now)-Sum(now-1);
if (cnt<=MAX&&Sum(cnt)-Sum(cnt-1)) ans++;
}
}printf("%d\n",ans);
}return 0;
}
除法分块+卡常题……我们可以处理出每个 $a_i$ 的分段点(值改变的点),然后从后往前处理:刚开始,所有点的分段点都是 $1$ ,随着不断往前,$a_i$ 会从 $a_i$ 变成 $\lfloor{a_i\over 2}\rfloor$(到达了下一个分段点),改变的次数即分段点的个数,总共有 $O(n\sqrt n)$ 个。我们只要在每次改变的时候修改一下贡献就行了。
但是会被卡常……所以我们可以预处理 $[1,10^5]$ 所有数的分段点,对于每次询问再预处理一下每个位置贡献改变多少就行了。
#include<cstdio>
#include<cctype>
#include<vector>
#define pb push_back
using namespace std;
typedef long long LL;typedef vector<int>::iterator vit;
const int maxn=100000;
int te,n,K,a[maxn+5],ans;vector<int> pos[maxn+5],val[maxn+5];LL num[maxn+5],sum;
#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
static char buf[100000],*l=buf,*r=buf;
return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
T tot=0;char ch=readc(),lst='+';
while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
int main(){
freopen("CHONQ.in","r",stdin);freopen("CHONQ.out","w",stdout);
for (int i=1;i<=maxn;pos[i].pb(i+1),val[i].pb(-1),i++)
for (int l=2,lst=i,now;l<=i;l=i/now+1)
now=i/l,pos[i].pb(l),val[i].pb(now-lst),lst=now;
for (readi(te);te;te--){
readi(n);readi(K);for (int i=1;i<=n;i++) readi(a[i]),num[i]=0;ans=n+1;sum=0;
for (int i=1;i<=n;i++)
for (vit P=pos[a[i]].begin(),V=val[a[i]].begin();P!=pos[a[i]].end()&&*P<=i;P++,V++) num[i-*P+1]+=*V;
for (int i=n;i;i--) if ((sum+=a[i]+num[i])<=K) ans=i;printf("%d\n",ans);
}return 0;
}
这题被LTL神仙秒了Orz。由于最多只能走两步,所以只能往回走一下马上走回来,或者一直跳着走,最后走回去。
因此我们可以做两次DP,第一次是正着的 $f_{i,0/1}$ 表示走到 $i$ ,$i-1$ 没走过/走过的方案数(记录 $0/1$ 是为了往回走一下以及之后跳回来,由于最多只能走两步所以只需要记录前一个就好了),那么:
$$ f_{i,1}=f_{i-1,0}+f_{i-1,1}+[a_{i-2}=2]f_{i-1,0}\\ f_{i,0}=[a_{i-2}=2](f_{i-2,0}+f_{i-2,1}) $$
其中 $[a_{i-2}=2]f_{i-1,0}$ 就是从 $i-1$ 往回走到 $i-2$ ,然后走到 $i$ 。
接下来要求出 $g_i$ 表示从 $i+1$ 开始往后走,最终走回 $i$ 的方案数(LTL神仙想到的状态Orz),那么 $f_{i+1,0}g_i$ 就对应着从 $1$ 走到 $i+1$ ,然后往后走,最终走回 $i$ 的方案数。
$$ g_{i}=[a_{i+1}=2\land a_{i+2}=2]g_{i+2}+[a_{i+2}=2]+1 $$
第一个表示从 $i+1$ 走到 $i+3$ ,往后走回到 $i+2$ ,然后从 $i+2$ 回到 $i$ ,第二个表示走到 $i+2$ 后立刻返回 $i$ ,第三个表示直接从 $i+1$ 走到 $i$ 。
#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=100000,MOD=1e9+7;
int te,n,a[maxn+5],f[maxn+5][2],g[maxn+5],ans;
#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
static char buf[100000],*l=buf,*r=buf;
return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
T tot=0;char ch=readc(),lst='+';
while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int main(){
freopen("CHEFSOC.in","r",stdin);freopen("CHEFSOC.out","w",stdout);
for (readi(te);te;te--){
readi(n);memset(a,0,sizeof(a));for (int i=1;i<=n;i++) readi(a[i]);f[1][0]=1;
for (int i=2;i<=n;i++){
f[i][0]=f[i][1]=0;AMOD(f[i][1],f[i-1][0]);AMOD(f[i][1],f[i-1][1]);
if (a[i-2]==2) AMOD(f[i][0],f[i-2][0]),AMOD(f[i][0],f[i-2][1]),AMOD(f[i][1],f[i-1][0]);
}g[n]=0;AMOD(ans=f[n][0],f[n][1]);
for (int i=n-1;i;i--){
AMOD(ans,f[i][0]);AMOD(ans,f[i][1]);g[i]=1;
if (a[i+1]==2&&a[i+2]==2) AMOD(g[i],g[i+2]);if (a[i+2]==2) AMOD(g[i],1);
AMOD(ans,(LL)f[i+1][0]*g[i]%MOD);
}printf("%d\n",ans);
}
return 0;
}
鬼畜题……显然有贪心,就是把深度从小到大排序之后依次代入公式,这样肯定是最大的。然后是法老发现了PTREE的性质:随着深度递增,节点数也递增。
所以把每个深度的节点个数按顺序拿出来,是一个不降序列,且节点个数相同的深度是连续的。假设深度在 $[L,R]$ 内的节点个数都是 $S$ ,那么我们要计算的式子是(设 $pre$ 表示深度在 $L$ 之前的节点总个数):
$$ V=\sum_{i=0}^{R-L}(L+i)\sum_{j=0}^{S-1}x^{pre+iS+j}\\ =\sum_{i=0}^{R-L}(L+i){x^{pre+iS}(x^{S}-1)\over x-1}\\ ={(x^{S}-1)\over x-1}\sum_{i=0}^{R-L}(L+i)x^{pre+iS}\\ $$
后面那个是一个等差数列乘上一个等比数列,可以利用错位相减求出前缀和:
$$ S_n=\sum_{i=0}^{n}(L+i)x^{pre+iS}\\ x^SS_n=\sum_{i=0}^{n}(L+i)x^{pre+(i+1)S}=\sum_{i=1}^{n+1}(L+i-1)x^{pre+iS}\\ S_n-x^SS_n=(L-1)x^{pre}-(L+n)x^{pre+(n+1)S}+\sum_{i=0}^{n}x^{pre+iS}\\ S_n={(L-1)x^{pre}-(L+n)x^{pre+(n+1)S}+{x^{pre}(x^{(n+1)S}-1)\over 1-x^S}\over 1-x^S}\\ V={(L-1)x^{pre}-(L+n)x^{pre+(n+1)S}+{x^{pre}(x^{(n+1)S}-1)\over 1-x^S}\over 1-x} $$
这样就可以做到 $O(log_210^9)$ 求出一个块内的值。
但是块数有多少呢?由于我们把相同的放在一起做,所以块数只有 $O(\sqrt n)$ ,如果能快速求出每个点的块,我们就可以做到 $O(q\sqrt nlog_210^9)$ 的复杂度。
其实块并不难求,直接暴力就行了!我们每次从重儿子继承块,然后暴力将轻儿子的信息合并进来就行了,复杂度 $O(nlog_2n+n\sqrt n)$ 。
但是……由于有 $O(log_210^9)$ 的存在……这样做就光荣的TLE了……因此我们需要快速求快速幂以及快速求逆元:
套上这两个东西,然后疯狂卡常(卡常By X_o_r),你就可以过了……
下面有两份代码,第一份比较可读(不能过,没有快速求逆元),第二份是卡常的产物(能过):
#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
#define pb push_back
using namespace std;
typedef long long LL;
const int maxn=200000,maxt=4e7,MOD=1e9+7;
int T,n,te,si[maxn+5],dep[maxn+5],MAX[maxn+5],SH[maxn+5],INV,ans;
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5];
int len,ro[maxn+5],ls[maxt+5],rs[maxt+5],sum[maxt+5],MIN[maxt+5];
#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
static char buf[100000],*l=buf,*r=buf;
return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
T tot=0;char ch=readc(),lst='+';
while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
inline void writei(int x){
static int buf[100],len=0;do buf[len++]=x%10,x/=10; while (x);
while (len) putchar(buf[--len]+48);puts("");
}
#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
void MakeSH(int x,int pre=0){
for (int j=(si[x]=1,MAX[x]=dep[x]=dep[pre]+1,SH[x]=0,lnk[x]),u;j;j=nxt[j])
if ((u=son[j])!=pre) MakeSH(u,x),MAX[x]=MAX[u],si[x]+=si[u],si[u]>si[SH[x]]?SH[x]=u:0;
}
#define Pushup(p) (MIN[p]=min(MIN[ls[p]],MIN[rs[p]]))
int Insert(int p,int pos,int l=1,int r=n){
int now=++len;ls[now]=ls[p];rs[now]=rs[p];sum[now]=sum[p]+1;if (l==r) return MIN[now]=sum[now],now;int mid=l+(r-l>>1);
if (pos<=mid) ls[now]=Insert(ls[p],pos,l,mid); else rs[now]=Insert(rs[p],pos,mid+1,r);Pushup(now);return now;
}
void Join(int x,int pre,int fa){
ro[fa]=Insert(ro[fa],dep[x]);
for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) Join(son[j],x,fa);
}
void Dfs(int x,int pre=0){
for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) Dfs(son[j],x);ro[x]=Insert(ro[SH[x]],dep[x]);
for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre&&son[j]!=SH[x]) Join(son[j],x,x);
}
int getnum(int p,int pos,int l=1,int r=n){
if (!p) return 0;if (l==r) return sum[p];int mid=l+(r-l>>1);
return pos<=mid?getnum(ls[p],pos,l,mid):getnum(rs[p],pos,mid+1,r);
}
int FindR(int p,int k,int l=1,int r=n){
if (l==r) return l;int mid=l+(r-l>>1);
return MIN[rs[p]]>k?FindR(ls[p],k,l,mid):FindR(rs[p],k,mid+1,r);
}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline int Count(int L,int R,int x,int num,int pre){
if (x==1) return ((LL)(L+R)*(R-L+1)>>1)*num%MOD;
int q=Pow(x,num),A=Pow(x,pre),B=Pow(q,R-L+1),ans=0;ans=(LL)A*(B-1)%MOD*Pow(q-1,MOD-2)%MOD;
AMOD(ans,(LL)A*(MOD+L-1)%MOD);AMOD(ans,MOD-(LL)A*B%MOD*R%MOD);return (LL)ans*INV%MOD;
}
inline int Ask(int x,int y,int ans=0){
INV=Pow((MOD+1-y)%MOD,MOD-2);
for (int L=dep[x],R,pre=0;L<=MAX[x];L=R+1){
int num=getnum(ro[x],L);R=FindR(ro[x],num);
AMOD(ans,Count(L-dep[x],R-dep[x],y,num,pre));pre+=num*(R-L+1);
}return ans;
}
int main(){
freopen("PTREE.in","r",stdin);freopen("PTREE.out","w",stdout);
for (MIN[0]=2e9,readi(T);T;T--){
readi(n);readi(te);E=0;for (int i=1;i<=n;i++) lnk[i]=0;
for (int i=1,x,y;i<n;i++) readi(x),readi(y),Add(x,y),Add(y,x);
len=0;for (int i=1;i<=n;i++) ro[i]=0;MakeSH(1);Dfs(1);ans=0;
for (int x,y;te;te--) readi(x),readi(y),x^=ans,y^=ans,writei(ans=Ask(x,y));
}return 0;
}
卡常的产物(畸形):
#include<cmath>
#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
#define pb push_back
using namespace std;
typedef long long LL;
const int maxn=200000,MOD=1e9+7,maxs=700;
int T,n,te,si[maxn+5],dep[maxn+5],MAX[maxn+5],SH[maxn+5],ans;
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5];
vector<int> que[maxn+5],pos[maxn+5],cnt[maxn+5];
bool vis[maxs+5];
#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
static char buf[100000],*l=buf,*r=buf;
return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
T tot=0;char ch=readc(),lst='+';
while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
inline void writei(int x){
static int buf[100],len=0;do buf[len++]=x%10,x/=10; while (x);
while (len) putchar(buf[--len]+48);puts("");
}
#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
void MakeSH(int x,int pre=0){
for (int j=(si[x]=1,MAX[x]=dep[x]=dep[pre]+1,SH[x]=0,lnk[x]),u;j;j=nxt[j])
if ((u=son[j])!=pre) MakeSH(u,x),MAX[x]=MAX[u],si[x]+=si[u],si[u]>si[SH[x]]?SH[x]=u:0;
}
void Dfs(int x,int pre=0){
for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) Dfs(son[j],x);
swap(que[x],que[SH[x]]);que[x].pb(1);int s=que[x].size()-1;
if (SH[x]&&si[x]==si[SH[x]]+1){
pos[x]=pos[SH[x]];cnt[x]=cnt[SH[x]];
if (que[x][s-1]>1) pos[x].pb(s),cnt[x].pb(1);return;
}
for (int j=lnk[x];j;j=nxt[j])
if (son[j]!=pre&&son[j]!=SH[x]) for (int k=0;k<s;k++) que[x][k]+=que[son[j]][k];
for (int i=(pos[x].pb(0),cnt[x].pb(que[x][0]),0);i<s;i++)
if (que[x][i]!=que[x][i+1]) pos[x].pb(i+1),cnt[x].pb(que[x][i+1]);
}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
#define PowX(num) ((LL)RP[(num)/S]*LP[(num)%S]%MOD)
inline LL mod(LL x){return (x%=MOD)<0?x+MOD:x;}
inline int Ask(int x,int y){
register int s[maxs+5],sv[maxs+5],INV[maxs+5],ans=0,inv=Pow((MOD+1-y)%MOD,MOD-2),S,LP[maxs+5],RP[maxs+5],top=0,len[maxs+5],l[maxs+5],r[maxs+5],Q[maxs+5];;
s[0]=1,S=ceil(sqrt(si[x])),*LP=*RP=1;
for (register int i=1;i<=S;i++) LP[i]=(LL)LP[i-1]*y%MOD;
for (register int i=1;i<=S;i++) RP[i]=(LL)RP[i-1]*LP[S]%MOD;
for (register int i=0,ss=pos[x].size(),L=0,R,mul=1;i<ss;L=R+1,++i)
R=MAX[x]-dep[x]-pos[x][i],len[++top]=cnt[x][i],l[top]=L,r[top]=R,
(Q[top]=PowX(len[top])-1)?vis[top]=true:(vis[top]=false,Q[top]=1),s[top]=(LL)s[top-1]*Q[top]%MOD;
sv[top]=Pow(s[top],MOD-2),INV[top]=(LL)sv[top]*s[top-1]%MOD;
for (int i=top-1;i;i--) INV[i]=(LL)(sv[i]=(LL)sv[i+1]*Q[i+1]%MOD)*s[i-1]%MOD;
for (register int i=1,pre=0,L,R,num,A,now,B;i<=top;pre+=num*(R-L+1),i++)
L=l[i],R=r[i],num=len[i],y==1?AMOD(ans,((LL)(L+R)*(R-L+1)>>1)*num%MOD),0:A=(LL)PowX(pre)*inv%MOD,now=num*(R-L+1),B=PowX(now),AMOD(ans,mod(L-(LL)B*R-1+(vis[i]?(LL)(B-1)*INV[i]:R-L+1))*A%MOD);
return ans;
}
int main(){
freopen("PTREE.in","r",stdin);freopen("PTREE.out","w",stdout);
for (readi(T);T--;){
readi(n),readi(te),E=0;for (int i=1;i<=n;i++) lnk[i]=0,que[i].clear(),pos[i].clear(),cnt[i].clear();
for (register int i=1,x,y;i<n;i++) readi(x),readi(y),Add(x,y),Add(y,x);MakeSH(1),Dfs(1);
for (register int i=1;i<=n;++i) reverse(pos[i].begin(),pos[i].end()),reverse(cnt[i].begin(),cnt[i].end());
ans=0;for (register int x,y;te;te--) readi(x),readi(y),x^=ans,y^=ans,writei(ans=Ask(x,y));
}return 0;
}