A. Magic Mirror
#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=1e2+; char s[maxn]; int main()
{
int t,i;
scanf("%d",&t);
while (t--)
{
scanf("%s",s);
for (i=;i<strlen(s);i++)
if (s[i]>='a' && s[i]<='z')
s[i]-=;
if (strcmp(s,"JESSIE\0")==)
printf("Good guy!\n");
else
printf("Dare you say that again?\n");
}
return ;
}
B. Mathematical Curse
#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+; ll a[maxn];
ll f[],l[],r[],LL=3e18,rr=-3e18;
int c[]; int main()
{
int t,n,m,i,j;
scanf("%d",&t);
while (t--)
{
scanf("%d%d%lld",&n,&m,&a[]);
for (i=;i<=n;i++)
scanf("%lld",&a[i]);
l[]=r[]=a[];
scanf("%c",&c[]);
for (i=;i<=m;i++)
{
scanf("%c",&c[i]);
l[i]=LL;
r[i]=rr;
} for (j=;j<=n;j++)
{
for (i=m;i>=;i--)
{
switch(c[i])
{
case '+':
if (l[i-]!=LL)
l[i]=min(l[i],l[i-]+a[j]);
if (r[i-]!=rr)
r[i]=max(r[i],r[i-]+a[j]);
break;
case '-':
if (l[i-]!=LL)
l[i]=min(l[i],l[i-]-a[j]);
if (r[i-]!=rr)
r[i]=max(r[i],r[i-]-a[j]);
break;
case '*':
if (l[i-]!=LL)
l[i]=min(l[i],min(l[i-]*a[j],r[i-]*a[j]));
if (r[i-]!=rr)
r[i]=max(r[i],max(l[i-]*a[j],r[i-]*a[j]));
break;
case '/':
if (a[j]!=)
{
if (l[i-]!=LL)
l[i]=min(l[i],min(l[i-]/a[j],r[i-]/a[j]));
if (r[i-]!=rr)
r[i]=max(r[i],max(l[i-]/a[j],r[i-]/a[j]));
}
break;
}
}
}
printf("%lld\n",r[m]);
}
return ;
}
/*
3
5 5 1000
1000 1000 1000 1000 1000
***** 5 5 1000
-1000 -1000 -1000 -1000 -1000
*****
*/
E. Jiu Yuan Wants to Eat
#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 ull unsigned long long
#define minv 1e-6
#define inf 1e9
#define pi 3.1415926536
#define nl 2.7182818284
const int maxn=1e5+; vector<int>e[maxn];
int fa[maxn],num;
int dep[maxn],siz[maxn],son[maxn],top[maxn];
int id[maxn];
bool vis[maxn];
int n;
ull add[maxn<<],mul[maxn<<],sum[maxn<<]; void dfs1(int d,int deep)
{
vector<int>::iterator j;
int dd;
vis[d]=;
siz[d]=;
dep[d]=deep;
son[d]=;
for (j=e[d].begin();j!=e[d].end();j++)
{
dd=*j;
if (!vis[dd])
{
fa[dd]=d;
dfs1(dd,deep+);
siz[d]+=siz[dd];
if (siz[dd]>siz[son[d]])
son[d]=dd;
}
}
} void dfs2(int d,int topd)
{
vector<int>::iterator j;
int dd;
id[d]=++num;
top[d]=topd;
if (son[d]!=)
{
dfs2(son[d],topd);
for (j=e[d].begin();j!=e[d].end();j++)
{
dd=*j;
if (fa[d]!=dd && son[d]!=dd)
dfs2(dd,dd);
}
}
} void build(int index,int l,int r)
{
add[index]=;
mul[index]=;
sum[index]=;
if (l!=r)
{
int m=(l+r)>>;
build(index<<,l,m);
build(index<<|,m+,r);
}
} void push_down(int index,int len)
{
///(xx*a+b)*c+d
add[index<<]=add[index<<]*mul[index]+add[index];
add[index<<|]=add[index<<|]*mul[index]+add[index]; mul[index<<]=mul[index<<]*mul[index];
mul[index<<|]=mul[index<<|]*mul[index]; sum[index<<]=sum[index<<]*mul[index]+add[index]*((len+)>>); ///
sum[index<<|]=sum[index<<|]*mul[index]+add[index]*(len>>); add[index]=;
mul[index]=;
} void update_add(int index,int l,int r,int x,int y,ull k)
{
if (x<=l && r<=y)
{
sum[index]+=k*(r-l+);
add[index]+=k;
return;
}
if (add[index]!= || mul[index]!=)
push_down(index,r-l+);
int m=(l+r)>>;
if (x<=m)
update_add(index<<,l,m,x,y,k);
if (m<y)
update_add(index<<|,m+,r,x,y,k);
sum[index]=sum[index<<]+sum[index<<|]; ///
} void update_mul(int index,int l,int r,int x,int y,ull k)
{
if (x<=l && r<=y)
{
sum[index]*=k;
add[index]*=k;
mul[index]*=k;
return;
}
if (add[index]!= || mul[index]!=)
push_down(index,r-l+);
int m=(l+r)>>;
if (x<=m)
update_mul(index<<,l,m,x,y,k);
if (m<y)
update_mul(index<<|,m+,r,x,y,k);
sum[index]=sum[index<<]+sum[index<<|];
} ull query(int index,int l,int r,int x,int y)
{
if (x<=l && r<=y)
return sum[index];
if (x>r || y<l)
return ;
if (add[index]!= || mul[index]!=)
push_down(index,r-l+);
int m=(l+r)>>;
return query(index<<,l,m,x,y)+query(index<<|,m+,r,x,y);
} void work1(int x,int y,ull k)
{
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]])
swap(x,y);
update_mul(,,n,id[top[x]],id[x],k);
x=fa[top[x]];
}
if (dep[x]<dep[y])
swap(x,y);
update_mul(,,n,id[y],id[x],k);
} void work2(int x,int y,ull k)
{
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]])
swap(x,y);
update_add(,,n,id[top[x]],id[x],k);
x=fa[top[x]];
}
if (dep[x]<dep[y])
swap(x,y);
update_add(,,n,id[y],id[x],k);
} void work3(int x,int y)
{
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]])
swap(x,y);
update_mul(,,n,id[top[x]],id[x],-);
update_add(,,n,id[top[x]],id[x],-);
x=fa[top[x]];
}
if (dep[x]<dep[y])
swap(x,y);
update_mul(,,n,id[y],id[x],-);
update_add(,,n,id[y],id[x],-);
} ull work4(int x,int y)
{
ull tot=;
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]])
swap(x,y);
tot+=query(,,n,id[top[x]],id[x]);
x=fa[top[x]];
}
if (dep[x]<dep[y])
swap(x,y);
tot+=query(,,n,id[y],id[x]);
return tot;
} int main()
{
int i,a,u,v,q,mode;
ull x;
while (~scanf("%d",&n))
{
for (i=;i<=n;i++)
e[i].clear();
memset(vis,,sizeof(vis)); for (i=;i<=n;i++)
{
scanf("%d",&a);
e[a].push_back(i);
}
dfs1(,);
num=;
dfs2(,); build(,,n); scanf("%d",&q);
while (q--)
{
scanf("%d",&mode);
if (mode==)
{
scanf("%d%d%llu",&u,&v,&x);
work1(u,v,x);
}
else if (mode==)
{
scanf("%d%d%llu",&u,&v,&x);
work2(u,v,x);
}
else if (mode==)
{
scanf("%d%d",&u,&v);
work3(u,v);
}
else
{
scanf("%d%d",&u,&v);
printf("%llu\n",work4(u,v));
}
}
}
return ;
}
/*
7
1 1 1 2 2 4
5
2 5 6 1
1 1 6 2
4 5 6
3 5 2
4 2 2
2
1
4
3 1 2
4 1 2
3 1 1
4 1 1
7
1 1 1 2 2 4
5
2 5 6 1
1 1 6 2
4 5 6
3 5 2
4 2 2
2
1
4
3 1 2
4 1 2
3 1 1
4 1 1 11
1 1 2 2 2 3 3 8 9 9
10
2 4 10 3
4 1 3
4 6 11 */
F. Modular Production Line
G. Give Candies
#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+; char s[maxn];
int a[maxn]; int main()
{
int t,len,i;
ll x,y,z;
scanf("%d",&t);
while (t--)
{
scanf("%s",s);
len=strlen(s);
for (i=;i<=len;i++)
a[i]=s[len-i]-;
x=;
for (i=len;i>=;i--)
x=(x*+a[i])%(mod-);
x=(x-+mod-)%(mod-);
y=;
z=;
while (x)
{
if (x & )
z=z*y%mod;
x>>=;
y=y*y%mod;
}
printf("%lld\n",z);
}
return ;
}
H. String and Times
I. Save the Room
#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=1e2+; int main()
{
int x,y,z;
while (~scanf("%d%d%d",&x,&y,&z))
{
if (x%== && y%== && z%==)
printf("No\n");
else
printf("Yes\n");
}
return ;
}
J. Participate in E-sports
1. 不同方法时间上的比较 二分和另外一种方法 (l=(l+n/l)/2 )
其实还有倍增2^k（是否加）-> 2^(k-1)（是否加）-> 2^(k-2)（是否加）… 用加法代替二分的除法，应该会快一点。。。
#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 main()
{
ll n=;
ll l,r,m,v;
int x=,y=;
bool vis; r=n;
while ()
{
x++;
if (r*r==n)
{
vis=;
break;
}
l=n/r;
if (l==r)
{
vis=;
break;
}
r=(l+r)>>;
} l=; r=n;
while ()
{
y++;
m=(l+r)>>;
v=m*m;
if (v==n)
{
vis=;
break;
}
if (l==r)
break;
if (v<n)
l=m+;
else
r=m-;
} printf("%d %d",x,y);
return ;
} /*
100
10 13 123456789
17 27
*/
2.n*(n+1)/2 的找规律
#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-10
#define inf 1e9
#define pi 3.1415926536
#define nl 2.7182818284
const ll mod=1e9+;//
const int maxn=1e5+; int main()
{
ll i;
double v;
for (i=;i<=;i++)
{
v=sqrt(i*(i+)/);
if (fabs(v-(ll)v)<minv)
printf("%lld\n",i);
}
return ;
}
前一半：二分
后一半：找规律，打表。记录index每一个长度(二进制)都有哪些值
import java.math.BigInteger;
import java.util.Scanner; public class Main {
public static void main(String[] args) {
boolean vis1,vis2;
Scanner in=new Scanner(System.in);
BigInteger b2=BigInteger.valueOf();
BigInteger b1=BigInteger.valueOf();
BigInteger b0=BigInteger.valueOf();
BigInteger []f=new BigInteger[];
int [][]num=new int[][];
String s100=new String();
BigInteger b100; int i,j,k,len,q,v;
BigInteger n,l,r,m; s100=s100+"";
for (i=;i<=;i++)
s100=s100+"";
b100=new BigInteger(s100); ///100位以内就可以，因为还要平方
f[]=BigInteger.valueOf();
f[]=BigInteger.valueOf();
i=;
while (true)
{
f[i]=f[i-].multiply(BigInteger.valueOf()).subtract(f[i-]);
if (f[i].compareTo(b100)>)
break;
i++;
} for (j=;j<=i-;j++)
{
f[j]=f[j].multiply(f[j]).add(b1);
len=f[j].bitLength();
num[len][]++;
num[len][num[len][]]=j;
} f[i]=BigInteger.valueOf(); //index=1
len=f[i].bitLength();
num[len][]++;
num[len][num[len][]]=i; k=i+;
f[i+]=BigInteger.valueOf();
f[i+]=BigInteger.valueOf();
i+=; while (true)
{
f[i]=f[i-].multiply(BigInteger.valueOf()).subtract(f[i-]);
if (f[i].compareTo(b100)>)
break;
i++;
} for (j=k;j<=i-;j++)
{
f[j]=f[j].multiply(f[j]);
len=f[j].bitLength();
num[len][]++;
num[len][num[len][]]=j;
} q=in.nextInt();
while (q-->)
{
n=in.nextBigInteger(); vis1=false;
l=b1; r=n;
while (l.compareTo(r)<=)
{
m=l.add(r).divide(b2);
v=m.multiply(m).compareTo(n);
if (v==)
{
vis1=true;
break;
}
if (v<)
l=m.add(b1);
else
r=m.subtract(b1);
} vis2=false;
len=n.bitLength(); for (i=;i<=num[len][];i++)
if (n.equals(f[num[len][i]])==true)
{
vis2=true;
break;
} if (vis1 && vis2)
System.out.println("Arena of Valor");
else if (vis1 && !vis2)
System.out.println("Hearth Stone");
else if (!vis1 && vis2)
System.out.println("* Royale");
else
System.out.println("League of Legends");
}
}
}
/*
272796309905283809401 2391711738256 */
P.S:
队友求模小质数。过了~
K. Transport Ship
#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=1e4+; ll er[],value=1e4;
ll f[maxn]; int main()
{
int t,n,q,i,j,v,c;
scanf("%d",&t);
er[]=;
for (i=;i<=;i++)
er[i]=er[i-]<<;
while (t--)
{
f[]=;
for (i=;i<=value;i++)
f[i]=;
scanf("%d%d",&n,&q);
while (n--)
{
scanf("%d%d",&v,&c);
for (i=;i<c;i++)
for (j=value;j>=er[i]*v;j--)
f[j]=(f[j]+f[j-er[i]*v])%mod;
}
while (q--)
{
scanf("%d",&i);
printf("%lld\n",f[i]);
}
}
return ;
}
L. Poor God Water
#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=1e2+; ll a[][],b[][],c[][]; void init()
{ int i,j;
for (i=;i<;i++)
for (j=;j<;j++)
a[i][j]=; a[][]=;
a[][]=;
a[][]=;
a[][]=;
a[][]=;
a[][]=;
a[][]=;
a[][]=;
a[][]=;
a[][]=;
a[][]=;
a[][]=;
a[][]=;
a[][]=;
a[][]=;
a[][]=;
a[][]=;
a[][]=;
a[][]=;
a[][]=; for (i=;i<;i++)
for (j=;j<;j++)
b[i][j]=;
for (i=;i<;i++)
b[i][i]=;
for (i=;i<;i++)
for (j=;j<;j++)
c[i][j]=;
} int main()
{
///%mod
///<3
ll n,r;
int t,i,j,k; // init();
// for (i=0;i<9;i++)
// for (j=0;j<9;j++)
// for (k=0;k<9;k++)
// c[i][j]=(c[i][j]+a[i][k]*a[k][j])%mod;
// r=0;
// for (i=0;i<9;i++)
// for (j=0;j<9;j++)
// r=(r+c[i][j])%mod;
//
// printf("%d\n",r);
// return 0; ///b:danwei result
///a:*** scanf("%d",&t);
while (t--)
{
init();
scanf("%lld",&n);
if (n==)
printf("3\n");
else
{
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;
} 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;
n>>=;
} r=;
for (i=;i<;i++)
for (j=;j<;j++)
r=(r+b[i][j])%mod;
printf("%lld\n",r);
}
}
return ;
}
/*
3
9
20
46
106
244
560
1286
2956
6794
15610
35866
82416
189384
435170
*/