B Element Swapping
如果（i,j）是答案，那么容易得到
两式子相除得到a[i]+a[j]，然后针对右式是否为0的情况讨论一下，再根据第一个式子去判断一下。
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3fLL
#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=100010;
int n,m,k;
ll sum[maxn],x,y,X,Y;
ll ans,ct,cnt,tmp,flag;
struct node
{ll v,id;bool operator<(node aa)const{return v<aa.v;}
}a[maxn];
int ok[maxn];
int main()
{int T,cas=1;scanf("%d",&T);while(T--){scanf("%d%lld%lld",&n,&X,&Y);x=X;y=Y;rep(i,1,n){ok[i]=0;scanf("%lld",&a[i].v);x-=(ll)i*a[i].v;y-=(ll)i*a[i].v*a[i].v;a[i].id=i;}sort(a+1,a+n+1);ans=0;if(x==0&&y) {puts("0");continue;}if(x==0&&y==0){int i=1;ll tmp=0;while(i<=n){tmp=0;int j=i;while(j<=n&&a[j].v==a[i].v) {j++;tmp++;}ans+=(tmp*(tmp-1))/2;i=j;}printf("%lld\n",ans);continue;}else if(y%x) {puts("0");continue;}else {int tim=1;y=y/x;int i=1,j=n;while(i<j){tim++;int k=i;ll tmp=0;ll cnt=0;while(k<j&&2LL*a[k].v==y&&a[k].v==a[i].v)k++;if(i!=k) {i=k;continue;}tmp=0;while(j>i&&a[j].v+a[i].v>y) j--;if(j==i) break;if(a[i].v+a[j].v!=y) {i++;continue;}if(x%(a[j].v-a[i].v)!=0) {i++;continue;}ll z=x/(a[j].v-a[i].v);//cout<<x<<" "<<a[j].v-a[i].v<<" "<<z<<endl;k=i;while(k<j&&a[k].v==a[i].v) {if((ll)a[k].id-z<=(ll)n&&(ll)a[k].id-z>0LL){ok[a[k].id-(int)z]=tim;//cout<<a[k].id<<" "<<z<<endl;}k++;}while(j>=k&&a[i].v+a[j].v==y) {if(ok[a[j].id]==tim) ans++;j--;}i=k;}}printf("%lld\n",ans);// if(flag) puts("Yes"); else puts("No");}return 0;
}
E Sequence in the Pocket
贪心，每次最大的能不动就不动，若值x动了，那么小于x的值一定都要按序提到前面去，所以一定是从最大值开始考虑，尽量不动，一个数只有在所有比它大的数的左面，这个数就可以不动，所以权值相同时，还要按下标排序。不过当遇到某数需要前移时，还需考虑，左面，权值相同，并且在所有比它大的数的左面的数不用移动。
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
const int maxn=100005;
int n,ans;
struct AA
{int rt,x;bool operator<(const AA&aa)const{if(x==aa.x) return rt<aa.rt;return x<aa.x;}
}pos[maxn];
int main()
{int t;scanf("%d",&t);while(t--){ans=0;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&pos[i].x);pos[i].rt=i;}sort(pos+1,pos+1+n);int l=0,r=1;for(int i=n-1;i>=1;i--){if(pos[i].rt>pos[i+1].rt) {for(int j=i-1;j>=1;j--){if(pos[j].x!=pos[i].x){r=j+1;break;}if(l==0&&pos[j].rt<pos[i+1].rt){l=j;}}ans=i;if(l!=0){ans-=l-r+1;}break;}}printf("%d\n",ans);}return 0;
}
F Abbreviation
签到
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int inf=0x3f3f3f3f;
double pi=3.141592653589793238462643383279502884;
const ll mod=1e9+7;
const int maxn=300005;
int main()
{int t;scanf("%d",&t);while(t--){char s[105];scanf("%s",s);int len=strlen(s);for(int i=0;i<len;i++){if(i==0)printf("%c",s[i]);else{if(s[i]=='a'||s[i]=='e'||s[i]=='i'||s[i]=='y'||s[i]=='o'||s[i]=='u')continue;elseprintf("%c",s[i]);}}printf("\n");}return 0;
}
G Lucky 7 in the Pocket
#include<bits/stdc++.h>
#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=200010;
int n,m,k;
int a[maxn],sum[maxn];
int c[maxn];
int ans,ct,cnt,tmp,flag;
char s[maxn];
int main()
{int T,cas=1;scanf("%d",&n);{ans=0; flag=1;//memset(c,0,sizeof(c));rep(i,1,n){scanf("%d",&m);while(1){if(m%7==0&&m%4!=0) break;m++;}printf("%d\n",m);}//printf("%d\n",ans);// if(flag) puts("Yes"); else puts("No");}return 0;
}
H Singing Everywhere
预处理一个前缀和表示前i个音有多少个跑掉，然后暴力枚举删掉哪个就行。复杂度O(n)。
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3fLL
#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=100010;
int n,m,k;
ll a[maxn],sum[maxn];
ll ans,ct,cnt,tmp,flag;
char s[maxn];
int main()
{int T,cas=1;scanf("%d",&T);while(T--){scanf("%d",&n);a[0]=a[n+1]=inf;sum[0]=0;rep(i,1,n) scanf("%lld",&a[i]);if(n<3) {puts("0");continue;}rep(i,1,n){sum[i]=sum[i-1]+(a[i]>a[i-1]&&a[i]>a[i+1]);}ans=sum[n];if(a[2]>a[1]&&a[2]>a[3])ans=min(ans,sum[n]-1);if(a[n-1]>a[n-2]&&a[n-1]>a[n])ans=min(ans,sum[n]-1);rep(i,2,n-1)ans=min(ans,sum[n]-sum[i+1]+sum[i-2]+(a[i-1]>a[i-2]&&a[i-1]>a[i+1])+(a[i+1]>a[i-1]&&a[i+1]>a[i+2]));printf("%lld\n",ans);// if(flag) puts("Yes"); else puts("No");}return 0;
}
I Fibonacci in the Pocket
大数，很容易发现斐波那契数列的前缀和奇偶性为 奇奇偶 奇奇偶 奇奇偶 奇奇偶
所以只需要模3判断一下即可。
import java.math.*;
import java.util.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Scanner;
public class Main {public static BigInteger zero=new BigInteger("0");public static void main(String[] args) {Scanner sc = new Scanner(System.in);//result.toString();int T,cas=1;int n,m,cnt=0;BigInteger tmp=new BigInteger("0");BigInteger aa=new BigInteger("0");BigInteger a=new BigInteger("0");BigInteger b=new BigInteger("0");BigInteger zero=new BigInteger("0");BigInteger one=new BigInteger("1");BigInteger two=new BigInteger("2");BigInteger three=new BigInteger("3");n=sc.nextInt();while(n>0){n--;a=sc.nextBigInteger();b=sc.nextBigInteger();tmp=a.mod(three);aa=b.mod(three);if(tmp.equals(two)&&!aa.equals(one))System.out.println(one);else if(!tmp.equals(two)&&aa.equals(one))System.out.println(one);else System.out.println(zero);}}
}
J Welcome Party
并查集+优先队列，朋友关系是双向的，不开心的人的数量就是关系图的块数，每个块，需且只需一个人不开心，剩下的人都可以通过关系一个个进屋，不至于不开心，所以并查集判断关系分块，选定不开心的人为下标最小的，让其成为块内最早进屋的，由此决定字典序最小。
然后就用优先队列，每次选择可以进屋的人中编号最小的让其进屋，
首先将所有不高兴的人进队列，选出最小的编号的人，让其先进屋，然后将其朋友，加入队列（后面都是没有加入队列的加入过队列即可），在选最小的
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
const int maxn=1000005;
int pre[maxn],ans,t[maxn];
int find(int x)
{int r=x;if(x==pre[x]) return x;elsereturn pre[x]=find(pre[x]);
}
void join(int x,int y)
{int fx=find(x);int fy=find(y);if(fx!=fy){ans--;//cout<<x<<" ! "<<y<<endl;if(fx<fy)pre[fy]=fx;else{pre[fx]=fy;}}return;
}
struct AA
{int v,next;
}pos[maxn*3];
int n,m,a,b,vis[maxn],f[maxn],num,k;
void add(int x,int y)
{pos[++num].v=y;pos[num].next=f[x];f[x]=num;pos[++num].v=x;pos[num].next=f[y];f[y]=num;
}
priority_queue<int,vector<int>, greater<int> >pq;
void dfs()
{while(!pq.empty()){int x=pq.top();k++;if(k==n)printf("%d\n",x);else printf("%d ",x);pq.pop();for(int i=f[x];i!=-1;i=pos[i].next){int v=pos[i].v;if(vis[v]) continue;else {vis[v]=1;pq.push(v);}}}return;
}
int main()
{int tt;scanf("%d",&tt);while(tt--){while(!pq.empty()) pq.pop();scanf("%d%d",&n,&m);k=0;ans=n;for(int i=1;i<=n;i++){pre[i]=i;vis[i]=0;f[i]=-1;}num=0;while(m--){scanf("%d%d",&a,&b);add(a,b);join(a,b);}printf("%d\n",ans);for(int i=1;i<=n;i++){if(vis[find(i)]==0){vis[find(i)]=1;pq.push(find(i));}else continue;}dfs();
// for(int i=1;i<n;i++)
// {
// printf("%d ",t[i]);
// }
// printf("%d\n",t[n]);}
}
K Strings in the Pocket
这个题其实很水。。。如果S串和T相同，则答案为回文子串个数（想想是不是）
如果不同，则从开头找到第一个不同的位置l，从最后找到第一个不同的位置r，如果l~r翻转不相同，则答案为0，否则若S[l-1]==S[r+1],则答案++,l--,r++。
#include <bits/stdc++.h>
#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 int
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
const int maxn=2000005;
char s[maxn],t[maxn];
int Len[maxn<<1],pos;
char tmp[maxn<<1];
int l,r;
ll ans;
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]);elseLen[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<<l<<" "<<r<<endl;ans+=((r-l+2)/2);}printf("%lld\n",ans);return ;
}
int main()
{int tt;scanf("%d",&tt);while(tt--){ans=0;scanf("%s%s",s,t);int n=strlen(s);l=-1;for(int i=0;i<n;i++){if(s[i]!=t[i]) {l=i;break;}}if(l!=-1){r=-1;for(int i=n-1;i>=0;i--){if(s[i]!=t[i]) {r=i;break;}}int j=r,ok=0;for(int i=l;i<=r;i++,j--){if(s[i]!=t[j]){ok=1;break;}}if(ok){printf("0\n");}else{ans=1;for(int i=1;i<=l&&r+i<n;i++){if(s[l-i]==s[r+i]) ans++;else break;}printf("%lld\n",ans);}}else///s==t的时候{int len=init(s);manacher(tmp,len);}}
}