题目大意：改变一个数的位置 把一个序列变成不下降序列
题解：
设置一个pre，如果破坏单调性，就把‘删除’这个。否则把pre修改为当前元素的值。
考试时这样得了90分，是因为我的做法只能过这样的数据
1 3 4 1 5 7 （这个序列移动的数字是第二个1）
不能过这样的
1 3 6 100 7 9 10 （这个序列按我的做法移动的是7，但是应该是移去100）
#include<iostream> #include<cstdio> #include<cstring> #define maxn 1000009 using namespace std; int n,pre,tot,a[maxn]; inline int read(){ char ch=getchar();int x=0,f=1; for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; for(;isdigit(ch);ch=getchar())x=x*10+ch-'0'; return x*f; } int main(){ freopen("sort.in","r",stdin); freopen("sort.out","w",stdout); n=read();pre=read(); for(int i=2;i<=n;i++){ a[i]=read(); if(a[i]<pre){ tot++; if(tot>1){ printf("NO "); return 0; } } else pre=a[i]; } printf("YES "); fclose(stdin);fclose(stdout); return 0; }
正解
在序列不单调时有两种情况。
红色的表示在这个位置发现和前面的序列不能连起来了。那么我们枚举是删去红色的还是删去蓝色的。
我没有考虑到情况一导致GG,因为我每次删去的红的，而情况一删去蓝的就可以。哦，你不用管移去的数
插到哪里，反正一定移动后单调了。
#include<iostream> #include<cstring> #include<cstdio> #define maxn 1000009 using namespace std; int n,js,a[maxn]; bool no; inline int read(){ char ch=getchar();int x=0,f=1; for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; for(;isdigit(ch);ch=getchar())x=x*10+ch-'0'; return x*f; } bool check(int pos){ for(int i=1;i<=n;i++){ if(i==pos)continue; if(i-1==pos){ if(a[i]<a[i-2])return false; }else if(a[i]<a[i-1])return false; } return true; } int main(){ n=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=2;i<=n;i++){ if(a[i]<a[i-1]){ if(check(i)||check(i-1)){ }else { no=true;break; } } } if(no)puts("NO "); else puts("YES "); return 0; }
题解：
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int a1,b1,a2,b2,a3,b3,a4,b4; int main(){ freopen("mod.in","r",stdin); freopen("mod.out","w",stdout); scanf("%d%d%d%d%d%d%d%d",&a1,&b1,&a2,&b2,&a3,&b3,&a4,&b4); for(register int i=0;i<=800000009;i++){ if((i-b1)%a1!=0)continue; if((i-b2)%a2!=0)continue; if((i-b3)%a3!=0)continue; if((i-b4)%a4!=0)continue; printf("%d ",i); fclose(stdin);fclose(stdout); return 0; } return 0; }
对于30%的数据，枚举x。其实我70暴力就是枚举的x.
对于60%的数据，中国剩余定理.
对于100%的数据，用扩展欧几里德将式子合并.
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define N 5 #define ll long long using namespace std; ll n,m[N],a[N],m1,e; ll read() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f; } ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1,y=0; return a; } ll r=exgcd(b,a%b,x,y),tmp; tmp=x,x=y,y=tmp-a/b*y; return r; } ll crt() { ll a1=a[1],a2,m2,d,c;m1=m[1]; for(ll i=2;i<=n;++i) { a2=a[i],m2=m[i]; c=a2-a1;ll x=0,y=0; d=exgcd(m1,m2,x,y); if(c%d) return -1; x=x*c/d; int mod=m2/d; x=(mod+x%mod)%mod; a1+=m1*x;m1*=mod; } return a1; } int main() { // freopen("mod.in","r",stdin); // freopen("mod.out","w",stdout); n=4; for(int i=1;i<=n;i++) m[i]=read(),a[i]=read(); printf("%lld ",crt()); return 0; }
题解：
#include<iostream> #include<cstdio> #include<cstring> #define maxn 10009 using namespace std; int sumedge,len,tot,head[maxn],sum[maxn][29]; char s[maxn]; struct Edge{ int x,y,nxt; Edge(int x=0,int y=0,int nxt=0): x(x),y(y),nxt(nxt){} }edge[maxn]; void add(int x,int y){ edge[++sumedge]=Edge(x,y,head[x]); head[x]=sumedge; } bool check(int l,int r){ while(l<r){ if(s[l++]!=s[r--])return false; } return true; } bool ok(int l,int r){ for(int i=1;i<=26;i++){ for(int j=i+1;j<=26;j++){ int k=sum[r][i]-sum[l-1][i]; int p=sum[r][j]-sum[l-1][j]; if(k&&p&&k==p)return true; } } return false; } int main(){ freopen("str.in","r",stdin); freopen("str.out","w",stdout); scanf("%s",s+1);len=strlen(s+1); for(int i=1;i<=len;i++){ for(int j=1;j<=26;j++)sum[i][j]=sum[i-1][j]; sum[i][s[i]-'a'+1]++; } for(register int i=1;i<=len;i++) for(int j=i+1;j<=len;j++) if(check(i,j))add(i,j); for(int x=1;x<=len;x++){ for(int i=head[x];i;i=edge[i].nxt){ int v=edge[i].y; if(ok(x,v))++tot; } } printf("%d ",tot); fclose(stdin); fclose(stdout); return 0; } /*abcbaabcba*/
#include <cstdio> #include <cstring> #include <algorithm> #include <map> using namespace std; typedef unsigned long long ULL; typedef long long LL; char s[10005]; ULL h[10005],rh[10005],pw[10005]; int L; ULL hs(int l,int r){ return h[r]-h[l-1]*pw[r-l+1]; } ULL rhs(int l,int r){ return rh[l] - rh[r+1]*pw[r-l+1]; } struct N{ int a[26]; bool ok(){ int b[26]; for(int i=0;i<26;i++) b[i]=a[i]; sort(b,b+26); for(int i=0;i<25;i++){ if(b[i]>0&& b[i] == b[i+1]) return true; } return false; } void clear(){ memset(a,0,sizeof a); } }; LL ans=0; map<ULL,LL> num; map<ULL,N> A; void solve_odd(){ for(int i=1;i<=L;i++){ int l = 1,r = min(i,L-i+1)+1; while(r-l>1){ int mid = (l+r)/2; if(hs(i-mid+1,i+mid-1)== rhs(i-mid+1,i+mid-1)) l=mid; else r=mid; } int p=l; int tmp = p; while(tmp>=1&&num.find(hs(i-tmp+1,i+tmp-1))==num.end()) tmp--; LL sum = 0; N st; st.clear(); if(tmp>=1){ sum=num[hs(i-tmp+1,i+tmp-1)]; st = A[hs(i-tmp+1,i+tmp-1)]; } while(tmp<p){ st.a[s[i+tmp]-'a']+= (tmp == 0?1:2); if(st.ok()) sum++; num[hs(i-tmp,i+tmp)] = sum; A[hs(i-tmp,i+tmp)] = st; tmp++; } ans+=sum; // printf("# %d %lld ",i,sum); } } void solve_even(){ A.clear(); num.clear(); for(int i=1;i<L;i++){ // printf("### %d ",i); int l = 1,r = min(i,L-i)+1; while(r-l>1){ int mid = (l+r)/2; if(hs(i-mid+1,i+mid)== rhs(i-mid+1,i+mid)) l=mid; else r=mid; } int p=l; int tmp = p; while(tmp>=1&&num.find(hs(i-tmp+1,i+tmp))==num.end()) tmp--; LL sum = 0; N st; st.clear(); // printf("## %d ",p); if(tmp>=1){ sum=num[hs(i-tmp+1,i+tmp)]; st = A[hs(i-tmp+1,i+tmp)]; } while(tmp<p){ // printf("# %d %lld ",tmp,sum); st.a[s[i+tmp+1]-'a']+= 2; if(st.ok()) sum++; num[hs(i-tmp,i+tmp+1)] = sum; A[hs(i-tmp,i+tmp+1)] = st; tmp++; } ans+=sum; // printf("# %d %lld ",i,sum); } } int main(){ freopen("str.in","r",stdin); freopen("str.out","w",stdout); scanf("%s",s+1); L=strlen(s+1); s[0]='#'; pw[0]=1; for(int i=1;i<=L;i++) pw[i] = pw[i-1]*13131 ; for(int i=1;i<=L;i++) h[i] = h[i-1]*13131 + s[i]; for(int i=L;i>=1;i--) rh[i] = rh[i+1]*13131 + s[i]; // printf("%llu %llu",hs(1,3),rhs(1,3)); solve_odd(); solve_even(); printf("%lld ",ans); fclose(stdout); return 0; } 标称（字符串+二分）