A-萤火虫

思路：

1. 我们只用操作1，是不是能贪心都前面n-k个数都是0。
2. 如果我们对于1<=i<=n，归为k个集合，即s[j]=s[i%k],我们每操作一次操作1，s[0]~s[k-1]都会一起加1或者减1，如果我们最后能减到都同时0，就说明成功了。
3. 而我们可以贪心到最后只剩k个数，那么他们就对应各自的s[j]，我们可以对最后这k个数操作一次操作1，尽可能多的使这一次将更多数变为0，剩下不为0的显然只能使用操作2，即答案。

#include <bits/stdc++.h>
using namespace std;
#define ll     long long
const int N = 2e5 + 10;ll a[N];
int main()
{int t;cin>>t;while (t--){int n,k,x;cin>>n>>k;fill(a,a+n+1,0);for (int i=0; i<n; ++i){cin>>x;a[i%k]+=x;//把数分为k个集合，每次操作1就等效对每个集合操作}if (k==1){cout<<0<<endl;continue;}sort(a,a+k);int len=0;int p=1;for (int i=1; i<k; ++i){if (a[i]==a[i-1])p++;else{len=max(p,len),p=1;//最后一次操作1尽可能使多的集合变为0}}len=max(p,len);cout<<k-len<<endl;}return 0;
}

 B-罗伯特

思路：

显然用bfs去跑即可 ，为了使一个点不要重复经过，我们可以记录每个点在方向f时的最短路是多少，只更新更短的

#include <bits/stdc++.h>
using namespace std;
#define ll     long long
#define int ll
typedef pair<int, int> pii;
const int N = 110;struct node
{int d,x,y,p,f;bool operator<(const node&k)const{return d>k.d;}
};
int dp[N][N][60][5];
bool vis[N][N][60][5];
int ways[5][3]= {{-1,0},{1,0},{0,-1},{0,1}};
pii mp[N][N];
char ch[N][N];
int32_t main()
{int n,m,p,k;cin>>n>>m>>k>>p;int x1,y1,x2,y2;for (int i=1; i<=k; ++i){cin>>x1>>y1>>x2>>y2;mp[x1][y1]= {x2,y2};mp[x2][y2]= {x1,y1};}memset(dp,0x3f,sizeof(dp));for (int i=1; i<=n; ++i)for (int j=1; j<=m; ++j){cin>>ch[i][j];if (ch[i][j]=='U')ch[i][j]='0';else if (ch[i][j]=='D')ch[i][j]='1';else if (ch[i][j]=='L')ch[i][j]='2';else if (ch[i][j]=='R')ch[i][j]='3';}priority_queue<node>q;dp[1][1][0][3]=0;q.push({0,1,1,0,3});while (!q.empty()){node u=q.top();q.pop();if (vis[u.x][u.y][u.p][u.f])continue;vis[u.x][u.y][u.p][u.f]=1;if (u.x==n&&u.y==m){cout<<"YES"<<endl;cout<<dp[u.x][u.y][u.p][u.f]<<endl;return 0;}if (ch[u.x][u.y]=='.'){for (int i=0; i<4; ++i){node v=u;v.x+=ways[i][0],v.y+=ways[i][1],v.p+=(i!=v.f);v.f=i;if (1<=v.x&&v.x<=n&&1<=v.y&&v.y<=m&&ch[v.x][v.y]!='#'){if (mp[v.x][v.y].first!=0){pii tmp=mp[v.x][v.y];v.x=tmp.first,v.y=tmp.second;}if (v.p<=p&&dp[v.x][v.y][v.p][v.f]>dp[u.x][u.y][u.p][u.f]+1){dp[v.x][v.y][v.p][v.f]=v.d=dp[u.x][u.y][u.p][u.f]+1;q.push(v);}}}}else if (('0'<=ch[u.x][u.y]&&ch[u.x][u.y]<='3')||ch[u.x][u.y]=='@'){node v=u;if (ch[u.x][u.y]!='@')v.f=ch[u.x][u.y]-'0';v.x+=ways[v.f][0],v.y+=ways[v.f][1];if (1<=v.x&&v.x<=n&&1<=v.y&&v.y<=m&&ch[v.x][v.y]!='#'){if (mp[v.x][v.y].first!=0){pii tmp=mp[v.x][v.y];v.x=tmp.first,v.y=tmp.second;}if (v.p<=p&&dp[v.x][v.y][v.p][v.f]>dp[u.x][u.y][u.p][u.f]+1){dp[v.x][v.y][v.p][v.f]=v.d=dp[u.x][u.y][u.p][u.f]+1;q.push(v);}}}}cout<<"NO"<<endl;return 0;
}

C-论AE自动化的重要性

思路：

裸拓扑，反向建边即可 

#include <bits/stdc++.h>
using namespace std;
#define ll     long long
#define int ll
const int N = 2e5 + 10;
const int mod=1e9+7;ll a[N],in[N];
struct node
{int next,to,w;
} edge[N<<1];
int head[N],num;void add(int u,int v,ll w)
{edge[++num].next=head[u];edge[num].to=v,edge[num].w=w;head[u]=num;
}int32_t main()
{int n,m,k;cin>>n>>m>>k;int x,y,c;for (int i=1; i<=k; ++i){cin>>x>>y;a[x]+=y;}for (int i=1; i<=m; ++i)cin>>x>>y>>c,add(y,x,c),in[x]++;queue<int>q;ll ans=0;for (int i=1; i<=n; ++i)if (!in[i])q.push(i);while (!q.empty()){int u=q.front();q.pop();ans=(ans+a[u])%mod;for (int i=head[u]; i; i=edge[i].next){int v=edge[i].to,w=edge[i].w;a[v]=(a[v]+a[u]*w)%mod;if (--in[v]==0)q.push(v);}}cout<<ans<<endl;return 0;
}

G-Clannad

 思路：

1. 目标是取n+1个不相同的数，使得这些数存在有两个数差是n倍数。因为n+1>n，所以如果这n个数mod n。必然有两个余数相同，那么他们的差绝对值就是n了
2. 所以问题转化为如果x>=n+1(使得可以取n+1个不同的数），那就是组合数，在x个数选n+1个数。所以预处理组合数即可

#include <bits/stdc++.h>
using namespace std;
#define ll     long long
#define endl             "\\n"
const int N = 5e3 + 10;
const int mod=1e9+7;ll c[N][N];
void init()
{c[0][0]=1;for (int i=1; i<=5e3; ++i){c[i][0]=1;for (int j=1; j<=i; ++j)c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;}
}int main()
{std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t,n,x;cin>>t;init();while (t--){cin>>n>>x;if (n+1>x){cout<<-1<<endl;continue;}else{cout<<c[x][n+1]<<endl;}}return 0;
}

H-性格差劲的久美子

思路：

1. 首先 如果a的数字b里面没有，显然这个数字排在哪里都可以。
2. 而对应x,y同时属于a与b数组，那么我们假设x在b中出现范围是L[x]~R[x],y范围是L[y]~R[y]，那么我们需要满足x,y在a的子串出现范围是R[y]<=L[x]
3. 所以我们可以先处理b中每个数在b的出现范围
4. 然后顺序遍历a。设t[i]表示在i位置之后出现了多少个位置
   1. 如果,那么显然答案子串可以直接无视顺序加它。
   2. 如果属于，那么a[i]可以匹配b中所有在a[i]最后一次出现后的数字+1（t记录的数字都是在a数组中在a[i]出现前的，我们这样加（表示他们都是在b中顺序是在a之后出现的）。然后再对a[i]第一次出现及其之前的位置更新t[i],表示这些区间可以出现a[i]
5. 因为维护区间数个数，每次都是单点修改，所以树状数组功能足够了

#include <bits/stdc++.h>
using namespace std;
#define ll     long long
#define endl             "\\n"
typedef pair<int, int> pii;
const int N = 2e5 + 10;
int t[N],a[N],b[N];
unordered_map<int,pii>mp;
void add(int x,int w)
{for (int i=x; i; i-=i&-i)t[i]=max(t[i],w);
}
int ask(int x)
{int ans=0;for (int i=x; i<=N; i+=i&-i)ans=max(ans,t[i]);return ans;
}int main()
{int n,m;cin>>n;for (int i=1; i<=n; ++i)cin>>a[i];cin>>m;for (int i=1; i<=m; ++i){cin>>b[i];if (!mp[b[i]].first)mp[b[i]]= {i,i};//更新每个在b中出现的数的出现区间else mp[b[i]].second=i;}int ans=0,sum=0;for (int i=1; i<=n; ++i){if (!mp[a[i]].first)sum++;//b中没出现直接加else{int tmp=ask(mp[a[i]].second)+1;//找符合条件的最长子串，寻找在b数组顺序在a[i]之后出现的数（这些数在a数组中是在a之前出现，先出现才能被加到t数组里面）ans=max(ans,tmp);add(mp[a[i]].first,tmp);//更新t数组中出现的数字的区间}}cout<<ans+sum<<endl;return 0;
}

K-因子模仿

思路：

注意到[l,r]胜利与否结果就是r是1还是0，所以 我们在区间操作中维护每个数被修改次数即可，奇数次转变奇偶性，偶数次等价没修改。所以其实是树状数组裸题

#include <bits/stdc++.h>
using namespace std;
#define ll     long long
#define endl             "\\n"
const int N = 1e6 + 10;
int t[N];
int n,q,x,op,l,r;
void add(int x,int w)
{for (int i=x; i<=n; i+=i&-i)t[i]+=w;
}
int ask(int x)
{int ans=0;for (int i=x; i; i-=i&-i)ans+=t[i];return ans;
}
int main()
{std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>n>>q>>x>>x>>x>>x;char c;for (int i=1; i<=n; ++i){cin>>c;if (c=='1')add(i,1),add(i+1,-1);}while (q--){cin>>op>>l>>r;if (op==1){add(l,1),add(r+1,-1);//区间修改}else{if (ask(r)&1)//单点查询{cout<<"Magical Splash Flare"<<endl;}else{cout<<"HoloPsychon"<<endl;}}}return 0;
}