Day1:T1
考场上觉得第二题比较水，于是就果断地跳进第二题的坑了，结果部分分都没来的及拿...
f[i][l]:用了i-n的数，这段子序列开始位置为l的方案数
考虑新加的一个数x，设原序列为S，
那么只会有三种放法：xSx,xxS,Sxx
对于限制条件，为了方便先把大于转小于
考虑三种转移
对于xSx:
f[i][l]+=f[i+1][l+1]
不能有以下限制：
h[l]<h[r],h[r]<h[l]
h[x]<=h[l],h[x]<=h[r] (l+1<=x<=r-1)
对于xxS:
f[i][l]+=f[i+1][l+2]
不能有以下限制:
h[l]<h[l+1] ,h[l+1]<h[l]
h[x]<=h[l],h[x]<=h[l+1] (l+2<=x<=r)
对于Sxx:
f[i][l]+=f[i+1][l]
不能有以下限制：
h[r]<h[r-1],h[r-1]<h[r]
h[x]<=h[r-1],h[x]<=h[r] (l<=x<=r-2)
对于小于号的条件直接判
对于小于等于号的条件，开一个二维前缀和数组，
那么就相当于判矩形内是否有点，有则不成立
#include<cstdio>
#include<cstring>
#include<algorithm>
const int maxn=2010;
using namespace std;
int n,m,s[maxn][maxn];long long f[maxn][maxn];bool t[maxn][maxn];char str[5];
int get(int x1,int y1,int x2,int y2){return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];}
void prework(){
memset(t,0,sizeof(t)),memset(s,0,sizeof(s));
for (int i=1,a,b;i<=m;i++){
scanf("%d%s%d",&a,str,&b);
if (str[0]=='>') swap(a,b),str[0]='<';
++s[a][b];
if (str[0]=='=') ++s[b][a];
else if (!str[1]) t[a][b]=1;
}
for (int i=1;i<=n*2;i++)
for (int j=1;j<=n*2;j++)
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
void dp(){
memset(f,0,sizeof(f));
for (int i=1;i<=(n<<1)-1;i++) f[n][i]=(!t[i][i+1]&&!t[i+1][i]);
for (int i=n-1;i;i--)
for (int l=1,r=(n-i+1)*2;r<=n*2;l++,r++){
if (!t[l][r]&&!t[r][l]&&!get(l+1,l,r-1,l)&&!get(l+1,r,r-1,r))//xSx
f[i][l]+=f[i+1][l+1];
if (!t[l][l+1]&&!t[l+1][l]&&!get(l+2,l,r,l+1))//xxS
f[i][l]+=f[i+1][l+2];
if (!t[r-1][r]&&!t[r][r-1]&&!get(l,r-1,r-2,r))//Sxx
f[i][l]+=f[i+1][l];
}
long long ans=f[1][1]%(1ll<<60);
if (ans<0) ans+=(1ll<<60);
printf("%I64d\n",ans);
}
int main(){
//freopen("dragon.in","r",stdin); freopen("dragon.out","w",stdout);
while (scanf("%d%d",&n,&m)!=EOF) prework(),dp();
return 0;
}
正解是考虑上1/8圆，x++时，y有可能-1,也有可能不减。
怎么避免大数开根呢，画图可知，只要判断(x+1,y-0.5)在圆内还是圆外即可
判圆内圆外就用x*x+y*y-r*r是小于0还是大于0
这样就可以通过只算乘法解决了
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
const int mod=1000000007;
using namespace std;
typedef long long ll;
ll r,r2,lim;int ans;
int main(){
//freopen("circle.in","r",stdin);freopen("circle.out","w",stdout);
scanf("%I64d",&r),r2=r*r,lim=(int)round(sqrt(1.0*r2/2));
ans=((int)round(sqrt(r2-lim*lim)))%mod;
if (ans>lim) ans+=lim,ans%=mod;
else if (ans<lim) ans=0;
ans+=((lim*(lim-1)/2)%mod),ans%=mod;
ans+=r,ans%=mod;
for (int x=0,y=r;x<lim-1;x++){
//if (1ll*x*x+2ll*x+1ll*y*y-y-1ll*r*r+1>=0) y--;
if (1.0*x*x+2.0*x+1.0*y*y-1.0*y+5.0/4.0-1.0*r2>0) y--;
ans+=y,ans%=mod;
}
printf("%d\n",ans);
return 0;
}
T3:恶心的SPFA题，考场上这题没写部分分，又坑了...
对于没有怪兽的情况，跑双关键字SPFA即可
对于怪兽的格子，因为怪兽只有一次伤害，所以对于与怪兽相邻的点，两两连距离为2，伤害为周围其他怪兽的伤害的边即可。
对于陷阱，就做点权即可。
细节比较多，还必须写Dijkstra+Heap优化才可以过...
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
#define mp(a,b) make_pair(a,b)
#define PI pair<int,int>
#define abs(a) (a>=0?a:-(a))
const int maxn=505,maxq=maxn*maxn*10,maxm=1100000;
const int dx[]={-maxn,-1,maxn,1};
using namespace std;
int n,m,stx,sty,edx,edy,pre[maxm],now[maxn*maxn],son[maxm],tot,st,ed;char map[maxn*maxn],s[maxn][maxn];
PI dis[maxn*maxn],val[maxm];
int P(int x,int y){return x*maxn+y;}
PI D(int x){return mp(x/maxn,x%maxn);}
void add(int a,int b,int bl,int dis){pre[++tot]=now[a],now[a]=tot,son[tot]=b,val[tot]=mp(bl,dis);}
bool check(int x){
int a=x/maxn,b=x%maxn;
if (a>n||a<=0||b>m||b<=0||map[x]=='#') return 0;
return 1;
}
bool near(int a,int b){
int x1=D(a).fi,y1=D(a).se,x2=D(b).fi,y2=D(b).se;
if (abs(x1-x2)+abs(y1-y2)<=1) return 1;
return 0;
}
PI operator +(PI a,PI b){return mp(a.fi+b.fi,a.se+b.se);}
struct node{
int x,b,d;
node( int x, int b, int d ){this->x=x,this->b=b,this->d=d;}
bool operator <(const node & xx)const{
if (b!=xx.b) return b>xx.b;
return d>xx.d;
}
};
void spfa(){
priority_queue<node> q;
q.push(node(st,0,0));
memset(dis,63,sizeof(dis));
dis[st]=mp(0,0);
while (!q.empty()){
int x=q.top().x;
if (x==ed) break;
q.pop();
for (int y=now[x];y;y=pre[y]){
PI tmp=dis[x]+val[y];
if (islower(map[son[y]])) tmp.fi+=map[son[y]]-'a'+1;
if (dis[son[y]]>tmp){
dis[son[y]]=tmp;
q.push(node(son[y],tmp.fi,tmp.se));
}
}
}
printf("%d %d\n",dis[ed].fi,dis[ed].se);
}
void prework(){
for (int i=1;i<=n;i++)//not monster
for (int j=1;j<=m;j++){
int x=P(i,j);
if (map[x]=='#'||isupper(map[x])) continue;
for (int k1=0;k1<=3;k1++){
int x1=x+dx[k1];
if (!check(x1)||isupper(map[x1])) continue;
int bl=0;
for (int k2=0;k2<=3;k2++){
int x2=x1+dx[k2];
if (!check(x2)) continue;
if (isupper(map[x2])) bl+=map[x2]-'A'+1;
}
add(x,x1,bl,1);
}
}
for (int i=1;i<=n;i++)//monster
for (int j=1;j<=m;j++){
int x=P(i,j);
if (isupper(map[x])){
for (int k1=0;k1<=3;k1++){
int x1=x+dx[k1];
if (!check(x1)) continue;
for (int k2=0;k2<=3;k2++) if (k2!=k1){
int x2=x+dx[k2];
if (!check(x2)) continue;
int bl=0;
for (int k3=0;k3<=3;k3++){
int x3=x2+dx[k3];
if (!check(x3)||near(x1,x3)) continue;
if (isupper(map[x3])) bl+=map[x3]-'A'+1;
}
add(x1,x2,bl,2);
}
}
}
}
}
int main(){
memset(map,'#',sizeof(map));
scanf("%d%d",&n,&m),scanf("%d%d%d%d",&stx,&sty,&edx,&edy),st=P(stx,sty),ed=P(edx,edy);
for (int i=1;i<=n;i++) scanf("%s",s[i]+1);
for (int i=0;i<=n+1;i++)
for (int j=0;j<=m+1;j++)
map[P(i,j)]=s[i][j];
prework(),spfa();
return 0;
}
Day2：T1树形DP。
设f[i][j]表示i号节点子树中距离为j的点的权值和，这可以递推求出。
然后对于每组询问(p,d)，就是子树中距离为d的点和+向上走i步的父亲的子树中距离为d-i的点的和 再减去走了回头路的点即可
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ls (j<<1)
#define rs ((j<<1)|1)
const int maxn=280000,maxt=44;
typedef long long ll;
using namespace std;
int n,Q,a[maxn],pow[maxt],dep,dis;ll ans,f[maxn][maxt];
int main(){
freopen("dream.in","r",stdin);freopen("dream.out","w",stdout);
scanf("%d%d",&n,&Q);
pow[0]=1;for (int i=1;i<=maxt-1;i++) pow[i]=pow[i-1]<<1;
for (int i=0;i<=maxt-1;i++) if (pow[i]-1==n){dep=i;break;}
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i=pow[dep-1];i<pow[dep];i++) f[i][0]=a[i];
for (int i=dep-1;i>=0;i--)
for (int j=pow[i-1];j<pow[i];j++){
f[j][0]=a[j];
for (int k=1;k<=dep;k++)
f[j][k]=f[j*2][k-1]+f[j*2+1][k-1];
}
// for (int i=1;i<=3;i++) printf("%d ",f[3][i]);puts("fuck");
for (int i=1,p,d;i<=Q;i++){
scanf("%d%d",&p,&d),ans=f[p][d];
if (d==0){printf("%d\n",a[p]);continue;}
for (dis=0;pow[dis]<=p;dis++);dis--;
if (d>dep+dis-1){puts("0");continue;}
if (dis==0){printf("%I64d\n",ans);continue;}
int ed=min(dis,d);
for (int j=1;j<ed;j++){
ans+=f[p>>j][d-j];
//printf("%d ",ans);
ans-=f[p>>(j-1)][d-j-1];
//printf("%d\n",ans);
}
if (d<=dis) ans+=a[p>>d];
else{
ans+=f[1][d-dis];
ans-=f[p>>(dis-1)][d-dis-1];
}
printf("%I64d\n",ans);
}
return 0;
}
T2：数论题，大致思路是类比辗转相除法，由f(a,b,l,r)得到f(b,a%b,x,y)就可以loga时间求出，但是推导过程想法很神...只知道推出来是对的，但是还不知道怎么想到这样推...考场上只拿了20分，不应该不拿另外40分部分分。
#include<cstdio>
#include<cstring>
#include<algorithm>
const int inf=2e9+10;
using namespace std;
ll a,b,s,l,r;int ans;
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int f(int a,int b,int l,int r){
if (!l) return 0;
if (r/a>(l-1)/a) return (l-1)/a+1;
int t=f(b,a%b,a-r%a,b-r%b);
return (l+1ll*b*t-1)/a+1;
}
int getans(int a,int b,int l,int r){
if (!a) return l?inf:0;
int t=gcd(a,b);if (r/g==(l-1)/g) return inf;
return f(a,b,l,r);
}
int main(){
//freopen("ice.in","r",stdin);freopen("ice.out","w",stdout);
scanf("%d",&T);
while (T--){
scanf("%I64d%I64d%I64d%I64d%I64d",&a,&b,&s,&l,&r);
l-=s,r-=s,a%=b;
/*if (l>r) r+=b;
if (r>=b) r-=b,l-=b;
if (r<=b) r+=b,l+=b;*/
if(l>r) r+=b; l-=s,r-=s;
if(r>=b) r-=b,l-=b; if(r<0) r+=b,l+=b;
if (l>=0) ans=getans(a,b,l,r);
else ans=min(getans(a,b,0,r),getans(a,b,l+b,b-1));
if (ans==inf) puts("Poor PPS.");
else printf("%d\n",ans);
}
return 0;
}
T3：考场上看到这题就放弃了，其实就是找黑白连通块数目就可以区分10个人了，剩下两个只要比较黑白区域的比例即可，代码也不是特别长。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define PI pair<int,int>
using namespace std;
const int maxn=905,maxq=maxn*maxn*5;
const int dx[]={1,1, 1,0, 0,-1,-1,-1};
const int dy[]={1,0,-1,1,-1, 1, 0,-1};
const char name[][15]={"Baekhyun","Chanyeol","Chen","D.O", "Kai","Kris","Lay","Luhan", "Sehun","Suho","Tao","Xiumin"};
const int bc[12]={9,5,1,1, 2,3,6,5, 5,2,2,5};
const int wc[12]={2,1,3,2, 13,1,2,8, 2,8,4,2};
int T,ans[2],cnt[2],cb,n,m,map[maxn][maxn],head,tail;bool bo[maxn][maxn];
PI q[maxq+10];
void bfs(int stx,int sty,int c){
head=0,q[tail=1]=mp(stx,sty),bo[stx][sty]=1;
while (head!=tail){
if (++head>maxq) head=1;
int x=q[head].fi,y=q[head].se;
for (int i=0;i<8;i++){
int nx=x+dx[i],ny=y+dy[i];
if (map[nx][ny]!=c||bo[nx][ny]) continue;
if (++tail>maxq) tail=1;
q[tail]=mp(nx,ny),bo[nx][ny]=1;
}
}
}
int main(){
scanf("%d",&T);
while (T--){
memset(bo,0,sizeof(bo)),memset(map,-1,sizeof(map)),cb=0,ans[0]=ans[1]=0;
scanf("%d%d",&n,&m);int col=0,num,x=1,y=0;
for (int i=1;i<=m;i++){
scanf("%d",&num),col^=1;
if (!col) cb+=num;
while (num--){
++y;if (y>n) y=1,x++;
map[x][y]=col;
}
}
for (int i=1;i<=n;i++) for (int j=1;j<=n;j++)
if (!bo[i][j]) ans[map[i][j]]++,bfs(i,j,map[i][j]);
if (ans[0]==5&&ans[1]==2){
if (cb*100<18*n*n) puts("Xiumin");
else puts("Sehun");
continue;
}
for (int i=0;i<12;i++)
if (ans[0]==bc[i]&&ans[1]==wc[i]){printf("%s\n",name[i]);break;}
}
return 0;
}