今天这场网络赛就比较舒服，（虽然一开始榜有点歪，但是基本上能做的题都做了）能A的题也不少，除了签到题，还有不少模板题，原题。最后还有一个贪心的题没有想出来，。做那么多题，也是真的有点累，（虽然套了几个板子，）
------------------------------------------(部分)题解------------------------------------------------
https://www.jisuanke.com/contest/3005?view=challenges
A. Who is better?
思路：看懂题意就很简单。怪物的数量用扩展中国剩余定理求出来，然后判输赢是斐波那契博弈。就两块的拼合。很简单。
但是一开始网上找的扩展中国剩余定理的板子，竟然WA了好多。最后发现竟然是，扩展中国剩余定理的板子问题，换个板子就Ａ了。
代码：
#include
typedef long long ll;
#define inf 0x3f3f3f3f3f3f3f3fLL
#define maxn 20
using namespace std;
int n;
ll M[100005],A[100005];
void ex_gcd(ll a,ll b,ll &d,ll&x,ll&y)
{
if(!b)
{
d=a;
x=1;
y=0;
}else{
ex_gcd(b,a%b,d,y,x);
y-=x*(a/b);
}
}
ll gcd(ll a,ll b)
{
return b==0?a:gcd(b,a%b);
}
ll CRT()
{
ll dm,i,a,b,x,y,d;
ll c,c1,c2;
a=M[0];
c1=A[0];
for(i=1;i { b=M[i]; c2=A[i]; ex_gcd(a,b,d,x,y); c=c2-c1; if(c%d) return -1; dm=b/d; x=((x*(c/d))%dm+dm)%dm; c1=a*x+c1; a=a*dm; } if(c1==0) { c1=1; for(i=0;i c1=c1*M[i]/gcd(c1,M[i]); } return c1; } ll nn,a,b,c; int main() { scanf("%d",&n); for(int i=0;i { scanf("%lld%lld",&M[i],&A[i]); } nn=CRT(); if(nn==-1) {printf("Tankernb!\n");return 0;} a=0;b=1; int ans=0; for(int i=1;a+b<=1e16;i++) { if(a+b==nn) {ans=1;break;} c=b; b=a+b; a=c; } if(ans==1) printf("Lbnb!\n"); else printf("Zgxnb!\n"); return 0; } B. so easy 思路:正解似乎是哈希+并查集思想,但是我用的map,竟然A了,然而后来发现,应该是T的..又交了几次源代码,确实卡了map的排序时间,用unordered_map就能A.这个题能A的那么快,也是人品爆棚! 代码: #include #define ll long long #define inf 0x3f3f3f3f3f3f3f3fLL #define maxn 100500 using namespace std; int n,q,z,x; map map int fin(int k) { if(k==-1) return -1; if(ma[k]==0) return k; else return ma[k]=fin(ma[k]); } int main() { scanf("%d%d",&n,&q); ma[n]=-1; while(q--) { scanf("%d%d",&z,&x); if(z==1) { ma[x]=x+1; } else if(z==2) { printf("%d\n",fin(x)); } } } C. Buy Watermelon 思路:水题,判奇偶,特判2就行. 代码: #include #define ll long long #define inf 0x3f3f3f3f #define rep(i,a,b) for(register int i=(a);i<=(b);i++) #define dep(i,a,b) for(register int i=(a);i>=(b);i--) using namespace std; const int maxn=2e5+5; //const double pi=acos(-1.0); //const double eps=1e-9; //const ll mo=1e9+7; int n,m,k; int a[maxn],c[maxn]; int ans,tmp,cnt; int flag; char s[maxn]; bool ok[maxn]; int main() { int T,cas=1; //scanf("%d",&T); while(scanf("%d",&n)!=EOF) { if(n&1) puts("NO"); else { if(n>=4) puts("YES"); else puts("NO"); } } return 0; } D. Carneginon 思路:kmp找字串,模板,找找关系判判就完了. 代码: #include #define ll long long #define inf 0x3f3f3f3f3f3f3f3fLL #define maxn 100500 using namespace std; void getnext(char *ch,int *next) { int x=strlen(ch); next[0]=0; for(int i=1,p=0;i { while(p>0&&ch[i]!=ch[p]) { p=next[p-1]; } if(ch[p]==ch[i]) p++; next[i]=p; } } int kmp(char *ch,char *chh,int *next)///查询ch内是否含有chh字串 { int n=strlen(ch),m=strlen(chh),j=0,i=0; while(i { if(ch[i]==chh[j]) { i++;j++; } else { if(j==0) i++; else j=next[j-1]; } } if(j==m) return 1; else return 0; } char t[maxn]; int q,a[maxn],b[maxn],n,m; char s[maxn]; int main() { scanf("%s",t); getnext(t,a); n=strlen(t); scanf("%d",&q); while(q--) { scanf("%s",s); m=strlen(s); if(n>m) { getnext(s,b); if(kmp(t,s,b)) {printf("my child!\n");} else {printf("oh, child!\n");} } else if(n==m) { int ok=0; for(int i=0;i { if(s[i]!=t[i]) {printf("friend!\n");ok=1;break;} } if(!ok) printf("jntm!\n"); } else if(n { if(kmp(s,t,a)) {printf("my teacher!\n");} else {printf("senior!\n");} } } } E. XKC's basketball team 思路: 先按w值排序.从大到小依次算答案,因为排序,queue也是从大到小入的队列,比当前i点的w+m大的,一定比剩下的w+m大,所以,继续往下寻找最右边的值>w+m的就可以. 代码: #include #define ll long long #define inf 0x3f3f3f3f3f3f3f3fLL #define maxn 500015 using namespace std; ll n,m,maxr,ans[maxn]; struct AA { ll w,rt; bool operator<(const AA&aa)const { if(w==aa.w) return rt>aa.rt; return w>aa.w; } }pos[maxn]; queue int main() { scanf("%lld%lld",&n,&m); for(int i=1;i<=n;i++) { scanf("%lld",&pos[i].w); pos[i].rt=i; } sort(pos+1,pos+1+n); maxr=-1; for(int i=1;i<=n;i++) { while(!q.empty()) { AA x=q.front(); if(x.w>=pos[i].w+m) { maxr=max(maxr,x.rt); q.pop(); } else break; } ans[pos[i].rt]=(maxr>pos[i].rt)?(maxr-pos[i].rt-1):(-1); q.push(pos[i]); } for(int i=1;i<=n;i++) { if(i==n) printf("%lld\n",ans[i]); else printf("%lld ",ans[i]); } } G. Colorful String 思路:马拉车,驾驾驾~ 代码: #include #define rep(i,a,b) for(register int i=(a);i<=(b);i++) #define dep(i,a,b) for(register int i=(a);i>=(b);i--) using namespace std; #define ll long long const ll mod=1e9+7; const int maxn=300015; char s[maxn],t[maxn]; int a[maxn]; int Len[maxn<<1],pos,qian[maxn][27]; char tmp[maxn<<1]; int l,r,len,cnt,num; int val[maxn]; ll ans; int search(int la,int lb,int x) { int l=la,r=lb; while(l { int mid=(l+r)>>1; if(qian[mid][x]-qian[la-1][x]>0) r=mid; else l=mid+1; } return r; } ll query(int l,int r) { ll sum=0; rep(k,0,25) { if(qian[r][k]-qian[l-1][k]>0) { int pos=search(l,r,k); //if(cnt==3) //cout< sum+=(r-pos+1); } } return sum; } int init(char *st) { int i,len=strlen(st); tmp[0]='@'; for(i=1;i<=2*len;i+=2) { tmp[i]='#'; tmp[i+1]=st[i/2]; } tmp[2*len+1]='#'; tmp[2*len+2]='$'; tmp[2*len+3]=0; return 2*len+1; } void manacher(char *st,int len) { int mx=0,po=0; for(int i=1;i<=len;i++) { if(mx>i) Len[i]=min(mx-i,Len[2*po-i]); else Len[i]=1; while(st[i-Len[i]]==st[i+Len[i]]) Len[i]++; if(Len[i]+i>mx) { mx=Len[i]+i; po=i; } l=(i-1)/2-(Len[i]-1)/2; r=(i-1)/2+(Len[i]-1)/2; if(Len[i]&1) r--; //cout< num=((r-l+2)/2); cnt=((i-1)/2)+1; if(cnt<=r+1) ans+=query(cnt,r+1); //if(l<=r) //cout< } printf("%lld\n",ans); return ; } int main() { int T,cas=1; scanf("%s",s); len=strlen(s); rep(i,0,len-1) { a[i]=s[i]-'a'; rep(j,0,25) qian[i+1][j]=qian[i][j]; qian[i+1][s[i]-'a']++; } memset(Len,0,sizeof(Len)); ans=0; len=init(s); manacher(tmp,len); //printf("%lld\n",ans); return 0; } /* babab */ K. Center #include #define rep(i,a,b) for(register int i=(a);i<=(b);i++) #define dep(i,a,b) for(register int i=(a);i>=(b);i--) using namespace std; #define ll long long const ll mo=5e6+7; const int maxn=2015; int a[maxn],n; ll x[maxn],y[maxn]; ll ans; map map ll mid(ll a,ll b) { return (a+b)/2; } int main() { int T,cas=1; scanf("%d",&n); rep(i,1,n) { scanf("%lld%lld",&x[i],&y[i]); x[i]*=2;y[i]*=2; mmp[x[i]*mo+y[i]]++; rep(j,1,i-1) mp[mid(x[i],x[j])*mo+mid(y[i],y[j])]++; } int ans=0; ll ansx=0,ansy=0; for(it=mp.begin();it!=mp.end();it++) { int num=(*it).second; if(num>ans) { ans=num; ansx=(*it).first/mo; ansy=(*it).first%mo; } } ans=n*2+5; x[++n]=ansx; y[n]=ansy; rep(j,1,n) { mmp.clear(); rep(i,1,n-1) mmp[x[i]*mo+y[i]]++; int as=0; rep(i,1,n-1) { ll xx=2*x[j]-x[i]; ll yy=2*y[j]-y[i]; if(mmp[xx*mo+yy]==0) { mmp[xx*mo+yy]++; as++; } } if(as } if(n==1) ans=0; printf("%d\n",ans); return 0; }