A. Hard to prepare
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <time.h>
#include <string>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <ext/rope>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long
#define minv 1e-6
#define inf 1e9
#define pi 3.1415926536
#define nl 2.7182818284
const ll mod=1e9+;//
const int maxn=1e5+; /**
0: x1<>xn and x1<>~xn
1: x1=xn
2: x1=~xn
**/ ll a[][],b[][],c[][]; ll mul(ll x,ll y)
{
ll r=;
while (y)
{
if (y & )
r=r*x%mod;
x=x*x%mod;
y>>=;
}
return r;
} int main()
{
int t,n,i,j,k;
ll z,v,vv,r; scanf("%d",&t);
while (t--)
{
scanf("%d%lld",&n,&z);
if (z==)
{
printf("2\n");
continue;
}
v=mul(,z);
if (n==)
{
printf("%lld\n",v);
continue;
} for (i=;i<;i++)
for (j=;j<;j++)
a[i][j]=;
a[][]=a[][]=a[][]=a[][]=;
a[][]=v-;
a[][]=v-;
a[][]=v-; for (i=;i<;i++)
for (j=;j<;j++)
b[i][j]=;
for (i=;i<;i++)
b[i][i]=; n-=;
while (n)
{
if (n & )
{
for (i=;i<;i++)
for (j=;j<;j++)
{
c[i][j]=b[i][j];
b[i][j]=;
}
for (i=;i<;i++)
for (j=;j<;j++)
for (k=;k<;k++)
b[i][j]=(b[i][j]+a[i][k]*c[k][j])%mod;
}
n>>=; for (i=;i<;i++)
for (j=;j<;j++)
{
c[i][j]=a[i][j];
a[i][j]=;
}
for (i=;i<;i++)
for (j=;j<;j++)
for (k=;k<;k++)
a[i][j]=(a[i][j]+c[i][k]*c[k][j])%mod;
} r=;
vv=v*(v-)%mod;
printf("%lld\n",(
vv*(b[][]+b[][])%mod
+v*(b[][]+b[][])%mod
+mod)%mod);
}
return ;
}
/*
5 2
244 1 3
8 2 3
56 3 3
344 4 3
2408 1 5
32 2 5
992 3 5
29792
*/
testA
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <time.h>
#include <string>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <ext/rope>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long
#define minv 1e-6
#define inf 1e9
#define pi 3.1415926536
#define nl 2.7182818284
const ll mod=1e9+;//
const int maxn=1e5+; int n=;
int k=;///2^z-1
int a[maxn];
int tot=; void dfs(int index)
{
int i;
if (index==n+)
{
if (a[n]+a[]!=k)
{
// for (i=1;i<=n;i++)
// printf("%d ",a[i]);
// printf("\n");
tot++;
}
return;
}
for (i=;i<=k;i++)
if (i+a[index-]!=k)
{
a[index]=i;
dfs(index+);
}
} int main()
{
a[]=-;
dfs();
printf("%d",tot);
return ;
}
/*
5 2
244 1 3
8 2 3
56 3 3
344 4 3
2408 1 5
32 2 5
992 3 5
29792
*/
B. BE, GE or NE
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <time.h>
#include <string>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <ext/rope>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long
#define minv 1e-6
#define inf 1e9
#define pi 3.1415926536
#define nl 2.7182818284
const ll mod=1e9+;//
const int maxn=1e3+;
const int maxm=2e2+; int f[maxn][maxm],dif=,n,l,r;
int a[maxn],b[maxn],c[maxn],last[maxm]; void dfs(int i,int x)
{
int y; if (a[i]!=)
{
y=min(x+a[i],);
if (i==n)
f[i+][y+dif]=last[y+dif];
else if (f[i+][y+dif]==- || f[i+][y+dif]==)
dfs(i+,y);
if (i & )
f[i][x+dif]=max(f[i][x+dif],f[i+][y+dif]);
else
f[i][x+dif]=min(f[i][x+dif],f[i+][y+dif]);
}
if (b[i]!=)
{
y=max(x-b[i],-);
if (i==n)
f[i+][y+dif]=last[y+dif];
else if (f[i+][y+dif]==- || f[i+][y+dif]==)
dfs(i+,y);
if (i & )
f[i][x+dif]=max(f[i][x+dif],f[i+][y+dif]);
else
f[i][x+dif]=min(f[i][x+dif],f[i+][y+dif]);
}
if (c[i]!=)
{
y=-x;
if (i==n)
f[i+][y+dif]=last[y+dif];
else if (f[i+][y+dif]==- || f[i+][y+dif]==)
dfs(i+,y);
if (i & )
f[i][x+dif]=max(f[i][x+dif],f[i+][y+dif]);
else
f[i][x+dif]=min(f[i][x+dif],f[i+][y+dif]);
}
} int main()
{
int m,i,j;
scanf("%d%d%d%d",&n,&m,&r,&l);
for (i=;i<=n;i++)
scanf("%d%d%d",&a[i],&b[i],&c[i]);
///Koutarou first max
for (i=;i<=n;i++)
for (j=;j<=;j++)
if (i & ) ///max
f[i][j]=-;
else
f[i][j]=; for (i=;i<=l+;i++)
last[i]=-;
for (i=r+;i<=;i++)
last[i]=; dfs(,m); if (f[][m+dif]==)
printf("Good Ending");
else if (f[][m+dif]==-)
printf("Bad Ending");
else
printf("Normal Ending");
return ;
}
C. Cacti Lottery
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <time.h>
#include <string>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <ext/rope>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long
#define minv 1e-6
#define inf 1e9
#define pi 3.1415926536
#define nl 2.7182818284
const ll mod=1e9+;//
const int maxn=1e6+; int n=,z[];
struct node
{
int a[],price;
int each[];
}f[maxn],cur;
bool vis[];
char s[];
int award[];
int number=;
int tot_know,tot_num,pos[maxn],each[];
int x,xx;
ll y;
double yy=; void DFS(int j)
{
int i;
if (j==n+)
{
int value=,k;
memset(vis,,sizeof(vis));
for (i=;i<=n;i++)
{
k=;
for (j=;j<cur.a[i];j++)
if (!vis[j])
k++;
value+=k*z[n-i];
vis[cur.a[i]]=;
}
f[value]=cur;
f[value].each[]=award[ cur.a[]+cur.a[]+cur.a[] ];
f[value].each[]=award[ cur.a[]+cur.a[]+cur.a[] ];
f[value].each[]=award[ cur.a[]+cur.a[]+cur.a[] ];
f[value].each[]=award[ cur.a[]+cur.a[]+cur.a[] ];
f[value].each[]=award[ cur.a[]+cur.a[]+cur.a[] ];
f[value].each[]=award[ cur.a[]+cur.a[]+cur.a[] ];
f[value].each[]=award[ cur.a[]+cur.a[]+cur.a[] ];
f[value].each[]=award[ cur.a[]+cur.a[]+cur.a[] ]; f[value].price=
max(
max(max(f[value].each[],f[value].each[]),
max(f[value].each[],f[value].each[])),
max(max(f[value].each[],f[value].each[]),
max(f[value].each[],f[value].each[])) );
return ;
} for (i=j;i<=n;i++)
{
swap(cur.a[j],cur.a[i]);
DFS(j+);
swap(cur.a[j],cur.a[i]);
}
} void init()
{
award[]= ;
award[]= ;
award[]= ;
award[]= ;
award[]= ;
award[]= ;
award[]= ;
award[]= ;
award[]= ;
award[]= ;
award[]= ;
award[]= ;
award[]= ;
award[]= ;
award[]= ;
award[]= ;
award[]= ;
award[]= ;
award[]= ;
cur.price=;
} /**
* :konw
# :don't konw
**/ void dfs2(int j)
{
int i;
if (j==tot_num+)
{
int value=,k;
memset(vis,,sizeof(vis));
for (i=;i<=n;i++)
{
k=;
for (j=;j<cur.a[i];j++)
if (!vis[j])
k++;
value+=k*z[n-i];
vis[cur.a[i]]=;
} for (i=;i<;i++)
each[i]+=f[value].each[i];
x++;
return ;
} for (i=j;i<=tot_num;i++)
{
swap(cur.a[pos[j]],cur.a[pos[i]]);
dfs2(j+);
swap(cur.a[pos[j]],cur.a[pos[i]]);
}
} void dfs1(int j)
{
int i;
if (j==tot_know+)
{
memset(each,,sizeof(each));
x=;
dfs2(j);
y=
max(
max(max(each[],each[]),
max(each[],each[])),
max(max(each[],each[]),
max(each[],each[])) ); xx++;
yy+=1.0*y/x;
///add have 10000 ... exit directly
return ;
} for (i=j;i<=tot_num;i++)
{
swap(cur.a[pos[j]],cur.a[pos[i]]);
dfs1(j+);
swap(cur.a[pos[j]],cur.a[pos[i]]);
}
} int main()
{
int t,i,j; init();
z[]=;
for (i=;i<=;i++)
z[i]=z[i-]*i; for (i=;i<=;i++)
cur.a[i]=i; DFS(); scanf("%d",&t);
while (t--)
{
scanf("%s",s+);
scanf("%s",s+);
scanf("%s",s+); memset(vis,,sizeof(vis));
x=,y=;
tot_know=;
for (i=;i<=;i++)
if (s[i]>='' && s[i]<='')
{
cur.a[i]=s[i]-;
vis[cur.a[i]]=;
}
else if (s[i]=='*')
{
tot_know++;
pos[tot_know]=i;
} tot_num=tot_know;
for (i=;i<=;i++)
if (s[i]=='#')
{
tot_num++;
pos[tot_num]=i;
} for (i=;i<=;i++)
if (s[i]=='#' || s[i]=='*')
{
for (j=;j<=;j++)
if (!vis[j])
break;
cur.a[i]=j;
vis[j]=;
} xx=;
yy=;
dfs1(); printf("%.10f\n",1.0*yy/xx);
}
return ;
}
/*
2
***
***
*** ##*
#*#
*##
*/
F. Features Track
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <time.h>
#include <string>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <ext/rope>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long
#define minv 1e-6
#define inf 1e9
#define pi 3.1415926536
#define nl 2.7182818284
const ll mod=1e9+;//
const int maxn=1e5+; struct node
{
int x,y,z;
}f[maxn]; int cmp(node a,node b)
{
if (a.x<b.x)
return ;
else if (a.x>b.x)
return ;
if (a.y<b.y)
return ;
else if (a.y>b.y)
return ;
if (a.z<b.z)
return ;
else
return ;
} int main()
{
int t,n,m,i,j,k,r;
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
j=;
for (i=;i<=n;i++)
{
scanf("%d",&m);
while (m--)
{
j++;
scanf("%d%d",&f[j].x,&f[j].y);
f[j].z=i;
}
}
sort(f+,f+j+,cmp); r=;
f[j+].x=f[j].x-;
k=;
for (i=;i<=j;i++)
{
if (f[i].x==f[i+].x && f[i].y==f[i+].y)
{
if (f[i].z==f[i+].z)
continue;
else if (f[i].z==f[i+].z-)
{
k++;
continue;
}
}
r=max(r,k);
k=;
}
printf("%d\n",r);
}
return ;
}
/*
3 8
2 1 1 2 2
2 1 1 1 4
2 1 1 2 2
2 2 2 1 4
0
0
1 1 1
1 1 1 5
1 1 1
2 2 2 1 1
3 1 1 1 1 1 1
1 2 3
1 1 1 5
1 1 1
2 2 2 1 3
3 1 1 1 1 1 1
1 2 3
1 1 1
*/
G. Trace
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <time.h>
#include <string>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <ext/rope>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long
#define minv 1e-6
#define inf 1e9
#define pi 3.1415926536
#define nl 2.7182818284
const ll mod=1e9+;//
const int maxn=5e4+; struct node
{
int v,num;
}x[maxn],y[maxn]; struct rec
{
int x,y;
}ff[maxn],f[maxn]; int vx[maxn],vy[maxn],s[maxn]; int cmp1(node a,node b)
{
return a.v>b.v;
} int main()
{
int n,i,j,value;
ll sum=; scanf("%d",&n);
// for (i=1;i<=n;i++)
for (i=n;i>=;i--)
scanf("%d%d",&ff[i].x,&ff[i].y);
ff[]={-,-}; memset(s,,sizeof(s));
for (i=;i<=n;i++)
{
x[i].num=i;
x[i].v=ff[i].x;
}
sort(x+,x+n+,cmp1);
j=;
for (i=;i<=n;i++)
{
if (ff[i].x!=ff[i-].x)
{
j++;
vx[j]=ff[i].x;
}
f[x[i].num].x=j;
f[x[i].num].y=ff[x[i].num].y;
}
for (i=;i<=n;i++)
{
value=;
j=f[i].x-;
while (j>)
{
value=max(value,s[j]);
j-=(j & (-j));
} sum+=f[i].y-value; j=f[i].x;
while (j<=n)
{
s[j]=max(s[j],f[i].y);
j+=(j & (-j));
}
} ///==========///
///y lisan
memset(s,,sizeof(s));
for (i=;i<=n;i++)
{
y[i].num=i;
y[i].v=ff[i].y;
}
sort(y+,y+n+,cmp1);
j=;
for (i=;i<=n;i++)
{
if (ff[i].y!=ff[i-].y)
{
j++;
vy[j]=ff[i].y;
}
f[y[i].num].y=j;
f[y[i].num].x=ff[y[i].num].x;
}
for (i=;i<=n;i++)
{
value=;
j=f[i].y-;
while (j>)
{
value=max(value,s[j]);
j-=(j & (-j));
} sum+=f[i].x-value; j=f[i].y;
while (j<=n)
{
s[j]=max(s[j],f[i].x);
j+=(j & (-j));
}
} printf("%lld",sum); return ;
}
/*
3
1 4
3 3
4 1 2
1 4
4 1
*/
H. Ryuji doesn't want to study
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <time.h>
#include <string>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <ext/rope>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long
#define minv 1e-6
#define inf 1e9
#define pi 3.1415926536
#define nl 2.7182818284
const ll mod=1e9+;//
const int maxn=1e5+; ll x[maxn],y[maxn],s[maxn]; int main()
{
int n,q,i,j,a,b,c;
ll sum;
scanf("%d%d",&n,&q);
for (i=;i<=n;i++)
{
scanf("%d",&s[i]);
j=i;
while (j<=n)
{
x[j]+=s[i];
y[j]+=1ll*s[i]*(n-i);
j+=(j & (-j));
}
} while (q--)
{
scanf("%d%d%d",&a,&b,&c);
if (a==)
{
sum=;
j=c;
while (j>)
{
sum+=y[j]-x[j]*(n-c-);
j-=(j & (-j));
}
j=b-;
while (j>)
{
sum-=y[j]-x[j]*(n-c-);
j-=(j & (-j));
}
printf("%lld\n",sum);
}
else
{
j=b;
while (j<=n)
{
x[j]-=s[b];
y[j]-=s[b]*(n-b);
j+=(j & (-j));
} j=b;
while (j<=n)
{
x[j]+=c;
y[j]+=1ll*c*(n-b);
j+=(j & (-j));
}
s[b]=c;
}
}
return ;
}
/*
5 5
1 2 3 4 5
1 2 5
2 3 -1
1 2 5
*/
I. Characters with Hash
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <time.h>
#include <string>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <ext/rope>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long
#define minv 1e-6
#define inf 1e9
#define pi 3.1415926536
#define nl 2.7182818284
const ll mod=1e9+;//
const int maxn=1e6+; char str[maxn]; int main()
{
// printf("%d\n",'z'-'o');
// printf("%d\n",'z'-'M');
// printf("%d\n",'z'-'l');
int t,len,v,i;
char c;
scanf("%d",&t);
while (t--)
{
scanf("%d %c",&len,&c);
scanf("%s",str); for (i=;i<len;i++)
if (str[i]!=c)
break;
if (i!=len && abs(c-str[i])<)
v=;
else
v=;
printf("%d\n",max(len*-i*-v,));
}
return ;
}
J. Maze Designer
/*
打通n*m-1个相邻的格子。
树：格子相当于一个点，相邻直接连通的格子有一条边
删去树的边，使用剩下的边，
所以使用最大生成树
*/
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <time.h>
#include <string>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <ext/rope>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long
#define minv 1e-6
#define inf 1e9
#define pi 3.1415926536
#define nl 2.7182818284
const ll mod=1e9+;//
const int maxn=5e2+;
const int maxt=maxn*maxn;
const int maxq=1e5+; struct rec
{
int x,y,z;
}e[maxt*]; struct node
{
int d,num;
node *next;
}*ask[maxt]; int z[maxt][],fa[maxt],dist[maxt],rd[maxq];
bool vis[maxt]; int getfather(int d)
{
if (fa[d]==d)
return d;
fa[d]=getfather(fa[d]);
return fa[d];
} void merge(int x,int y)
{
x=getfather(x);
y=getfather(y);
fa[y]=x;
} void dfs(int d)
{
int i,dd;
node *r=ask[d];
vis[d]=;
for (i=;i<=z[d][];i++)
{
dd=z[d][i];
if (!vis[dd])
{
dist[dd]=dist[d]+;
dfs(dd);
merge(d,dd);
}
}
while (r)
{
dd=r->d;
if (vis[dd])
rd[r->num]=dist[d]+dist[dd]-*dist[getfather(dd)];
r=r->next;
}
} int cmp(rec a,rec b)
{
return a.z>b.z;
} int main()
{
int n,m,q,Q,x,y,g=,num,i,j,a,b,c,d,d1,d2;
char c1,c2;
node *p;
scanf("%d%d\n",&n,&m); g=;
num=;
for (i=;i<n;i++)
for (j=;j<m;j++)
{
scanf("%c %d %c %d\n",&c1,&d1,&c2,&d2);
if (c1=='D')
{
e[++g].x=num;
e[g].y=num+m;
e[g].z=d1;
} if (c2=='R')
{
e[++g].x=num;
e[g].y=num+;
e[g].z=d2;
} num++;
}
sort(e+,e+g+,cmp); for (i=;i<n*m;i++)
fa[i]=i;
j=n*m-;
for (i=;j;i++)
{
while ()
{
x=getfather(e[i].x);
y=getfather(e[i].y);
if (x!=y)
break;
i++;
} fa[x]=y;
j--; z[e[i].x][]++;
z[e[i].x][z[e[i].x][]]=e[i].y; z[e[i].y][]++;
z[e[i].y][z[e[i].y][]]=e[i].x;
} scanf("%d",&q);
for (Q=;Q<=q;Q++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
a--,b--,c--,d--; a=a*m+b;
c=c*m+d; p=new node();
p->d=c;
p->num=Q;
p->next=ask[a];
ask[a]=p; p=new node();
p->d=a;
p->num=Q;
p->next=ask[c];
ask[c]=p;
} for (i=;i<n*m;i++)
fa[i]=i;
dfs(); for (i=;i<=q;i++)
printf("%d\n",rd[i]);
return ;
}