这么多模拟赛都没整理，能整理一天算一天吧qaq
sol:应该不难吧，分别对横坐标和纵坐标取差的绝对值，易知：如果互质就可以看到，否则就不行。然后出题人很毒瘤要用unsigned long long。
#include <cstdio> #include <algorithm> using namespace std; long long x1,y1,x2,y2,c1=0,c2=0; unsigned long long x,y; unsigned long long ABS(long long x,long long y) { if(x<y)swap(x,y); if(y>0)return x-y; return (unsigned long long)(x)+(unsigned long long)(-y); } inline unsigned long long gcd(unsigned long long x,unsigned long long y){return (y==0)?x:gcd(y,x%y);} int main() { while(~scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2)) { x=ABS(x1,x2); y=ABS(y1,y2); if(x==0)if(y>1)puts("NO"),c2++;else puts("YE5"),c1++; else if(y==0)if(x>1)puts("NO"),c2++;else puts("YE5"),c1++; else if(gcd(x,y)==1)puts("YE5"),c1++;else puts("NO"),c2++; }if(c1>c2)puts("Poor xshen!");else if(c1==c2)puts("Friend Ship.");else puts("Yahoo!"); }
sol：这就是大模拟啊，我代码在全班算很短了，我就简单说说模拟的方法，也没什么：我发现绝对值小于1e12，于是可以特判1e8一档，1e4一档，最后在一档,然后写一个过程负责输出一个四位数，不够就可以补零，然后拆成四位的样子逐个输出，再对应的输出单位如'Y','W'等。看代码吧out（补零的）和pout（不补零的）。
#include <cstdio> #include <cstring> #include <iostream> using namespace std; #define int long long char re[100005],ss[100005],sss[100005],ssss[100005]; int n; inline void out(int x) { bool bo=0; if(x==0){putchar('0');return;} if(x%1000==0){printf("%lld",x/1000),putchar('Q');return;} if(x%100==0&&x<1000){printf("0%lld",x/100),putchar('B');return;} if(x%10==0&&x<100){printf("0%lld",x/10),putchar('S');return;} if(x<10){printf("0%lld",x);return;} if(x>=1000)printf("%lld",x/1000),putchar('Q'),bo=0,x%=1000;else if(!bo&&x)putchar('0'),bo=1; if(x>=100)printf("%lld",x/100),putchar('B'),bo=0,x%=100;else if(!bo&&x)putchar('0'),bo=1; if(x>=10)printf("%lld",x/10),putchar('S'),bo=0,x%=10;else if(!bo&&x)putchar('0'),bo=1; if(x>=1)printf("%lld",x/1),bo=0;else if(!bo&&x)putchar('0'),bo=1; } inline void pout(int x) { if(x==0){putchar('0');return;} if(x%1000==0){printf("%lld",x/1000),putchar('Q');return;} if(x%100==0&&x<1000){printf("%lld",x/100),putchar('B');return;} if(x%10==0&&x<100){printf("%lld",x/10),putchar('S');return;} if(x<10){printf("%lld",x);return;} bool bo=1; if(x>=1000)printf("%lld",x/1000),putchar('Q'),bo=0,x%=1000;else if(!bo&&x)putchar('0'),bo=1; if(x>=100)printf("%lld",x/100),putchar('B'),bo=0,x%=100;else if(!bo&&x)putchar('0'),bo=1; if(x>=10)printf("%lld",x/10),putchar('S'),bo=0,x%=10;else if(!bo&&x)putchar('0'),bo=1; if(x>=1)printf("%lld",x/1),bo=0;else if(!bo&&x)putchar('0'),bo=1; } inline void write(char *s,int opt) { int i,j,num=0LL,boo; n=strlen(s+1); int pp=0,bo; i=1; bool ooo=0; while(s[i]=='+'||s[i]=='-') { pp+=(s[i]=='-'); i++; }bo=0; bool arr=0; int oo=0; if(pp&1&&!opt)for(j=1;j<=n;j++)if(isdigit(s[j])){putchar('F');break;}for(;i<=n;i++) if(s[i]!='.')num=num*10LL+(s[i]-'0');else break; if(num>0) { if(num>=100000000) { pout(num/100000000); putchar('Y'); num%=100000000; if(num)out(num/10000); if(num/10000)putchar('W'); num%=10000; if(num)out(num); } else if(num>=10000) { pout(num/10000); putchar('W'); num%=10000; if(num)out(num); }else pout(num); }else putchar('0'); if(s[i]=='.') { boo=0; int las=0; for(j=i+1;j<=n;j++){if(s[j]!='0'){boo=1; break;}} if(boo) { putchar('D'); las=n; for(las=n;las>=i+1;las--)if(s[las]!='0')break; for(j=i+1;j<=las;j++)putchar(s[j]); }else return; }else return; } inline int check(char *s){int i=1,pp=0; while(s[i]=='+'||s[i]=='-'){pp+=(s[i]=='-');i++;} return (pp&1)?-1:1;} signed main() { scanf("%s",re+1); int i,j,num=0LL,flg=0,boo=0; n=strlen(re+1); for(i=1;i<=n;i++)if(isdigit(re[i])&&re[i]!='0'){boo=1;break;} if(!boo)return putchar('0'),0; for(i=1;i<=n;i++){if(re[i]=='/'){flg=1;break;}} if(flg) { int cnt=0,num=0,oo=0; for(i=1;i<=n;i++){if(re[i]!='/')ss[++cnt]=re[i];else break; if(isdigit(re[i]))oo=oo*10+(re[i]-'0');} if(!oo)return putchar('0'),0; cnt=0; n=strlen(re+1); for(j=i+1;j<=n;j++){sss[++cnt]=re[j];if(isdigit(re[j]))num=num*10+re[j]-'0';} if((check(ss)<0||check(sss)<0)&&(check(ss)>0||check(sss)>0))putchar('F'); if(num!=1) {write(sss,1); putchar('f');putchar('z');} write(ss,1); }else write(re,0); }
sol:可以对每个k开一颗动态开点线段树，存入每个颜色的方案数，把每个点的方案数弄个前缀和一样的东西存起来，然后当前点的方案数就是左上角矩阵的前缀和减去当前点的方案数，见代码。
#include <cstdio> #include <cstring> using namespace std; const int N=1005,md=1000000007; int n,m,k,a[N][N],f[N][N],s[N][N],rt[N*N],cnt=0; struct segtree{int sum,ls,rs;}Tree[N*N*8]; inline void ins(int &x,int l,int r,int po,int v) { if(x==0)x=++cnt; (Tree[x].sum+=v)%=md; if(l==r)return; int mid=(l+r)>>1; if(po<=mid)ins(Tree[x].ls,l,mid,po,v); else ins(Tree[x].rs,mid+1,r,po,v); } inline int que(int l,int r,int ql,int qr,int x) { if(x==0||ql>qr)return 0; if(l==ql&&r==qr)return Tree[x].sum%md; int mid=(l+r)>>1,re=0; if(qr<=mid)return que(l,mid,ql,qr,Tree[x].ls)%md; else if(ql>mid)return que(mid+1,r,ql,qr,Tree[x].rs)%md; else return (que(l,mid,ql,mid,Tree[x].ls)%md+que(mid+1,r,mid+1,qr,Tree[x].rs)%md)%md; } signed main() { int i,j; scanf("%d%d%d",&n,&m,&k); memset(f,0,sizeof f); memset(rt,0,sizeof rt); for(i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&a[i][j]); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(i==1&&j==1){f[i][j]=s[i][j]=1;continue;} (f[i][j]+=(s[i-1][j-1]-que(1,m,1,j-1,rt[a[i][j]])%md+md)%md)%=md; s[i][j]=(((s[i-1][j]+s[i][j-1])%md-s[i-1][j-1]+f[i][j])%md+md)%md; }for(j=1;j<=m;j++) ins(rt[a[i][j]],1,m,j,f[i][j]%md); }printf("%d ",f[n][m]%md); }