A. Equal or Not Equal

题意：有一个序列首尾相连，如果两数相等就是E，否则N。现在给定字符序列，问是否存在这样的数字序列

思路:如果这个序列只有一个N那么数字序列怎么样都不可能，如果其他情况，都可以构造出来。

#include<bits/stdc++.h>
using namespace std;
int t;
string s;
int main(){cin>>t;while(t--){cin>>s;cout<<(count(s.begin(),s.end(),'N')==1 ? "NO\n":"YES\n");}return 0;
}

B. Triangles on a Rectangle

很简单，直接找四条边的最长距离乘以对应的高（矩形的长或者宽）更新最大值。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF=0x7fffffff;
int t;
int x[1000000];
signed main(){cin>>t;while(t--){int k,w,h,ans=-INF;cin>>w>>h;for(int i=0;i<4;i++){cin>>k;int minn=INF,maxn=-INF;for(int j=0;j<k;j++){cin>>x[j];minn=min(minn,x[j]);maxn=max(maxn,x[j]);if(i<2) ans=max(ans,(maxn-minn)*h);else ans=max(ans,(maxn-minn)*w);}}cout<<ans<<endl;	}return 0;
}

C. BA-String

给你一个字符串(只含a,*), 将其中的*替换成[ 0 , k ] 个b，问你所有情况中字典序第x 小的是什么。

#include<bits/stdc++.h>
using namespace std;
int n,k;
long long x; 
int main(){ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);int T;cin>>T;while(T--){cin>>n>>k>>x;string str;cin>>str;x--;reverse(str.begin(),str.end());int cnt=0;string res;for(auto s:str){if(s=='a'){res+=string(x % (cnt*k+1),'b');x/=(cnt*k+1);res+='a';cnt=0;}else cnt++;}res+=string(x%(cnt*k+1),'b');reverse(res.begin(),res.end());cout<<res<<endl;}return 0;
}

D. Exact Change（贪心+枚举）

给你一些数，你有1元、2元、3元三种硬币，问你最少带多少个硬币可以将这些数都可以分别凑出来。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
const int INF=0x3f3f3f3f;
int n;
int a[N];
int main(){ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);int T;cin>>T;while(T--){cin>>n;for(int i=0;i<n;i++) cin>>a[i];int res=INF; for(int x1=0;x1<=1;x1++){for(int x2=0;x2<=2;x2++){int ans=0;for(int i=0;i<n;i++){int cnt=INF;for(int sx1=0;sx1<=x1;sx1++){for(int sx2=0;sx2<=x2;sx2++){int v=a[i]-sx1-sx2*2;if(v>=0&&v%3==0){cnt=min(cnt,v/3);}}}ans=max(ans,cnt);}res=min(res,ans+x1+x2);}}cout<<res<<endl;}return 0;
}

E. Replace the Numbers

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
const int INF=0x3f3f3f3f;
int n;
int a[N],f[N],vis[N],num[N];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);
}
int main(){ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);int T;cin>>T;for(int i=1;i<=T;i++){int op; cin>>op;if(op==1){int x; cin>>x;a[++n]=i,f[i]=i,vis[i]=x;if(num[x]) f[i]=num[x];else num[x]=i;}else{int x,y; cin>>x>>y;if(x!=y&&num[x]){if(num[y]){f[num[x]]=num[y];num[x]=0;}else{num[y]=num[x];vis[num[x]]=y;num[x]=0;}}}}for(int i=1;i<=n;i++){cout<<vis[find(a[i])];cout<<(i==n?'\n':' ');}return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
const int INF=0x3f3f3f3f;
int n;
int a[N][3];
vector<int> ve;
int f[N];
int main(){ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);cin>>n;for(int i=1;i<=n;i++){cin>>a[i][0];if(a[i][0]==1) cin>>a[i][1];else cin>>a[i][1]>>a[i][2];} for(int i=n;i;i--){if(a[i][0]==1){if(!f[a[i][1]]) ve.push_back(a[i][1]);else ve.push_back(f[a[i][1]]);}else{if(!f[a[i][2]]) f[a[i][1]]=a[i][2];else f[a[i][1]]=f[a[i][2]];}}reverse(ve.begin(),ve.end());for(auto x:ve) cout<<x<<" ";cout<<endl;return 0;
}

F. Bipartite Array(待补)

//std1
#include <bits/stdc++.h>using namespace std;#define forn(i, n) for (int i = 0; i < int(n); ++i)const int INF = 1e9;
const int N = 1000 * 1000 + 13;int n;
int p[N], a[N];
int dp[N][2][2];
pair<int, int> pr[N][2][2];void solve() {scanf("%d", &n);forn(i, n) scanf("%d", &p[i]);forn(i, n) forn(pos, 2) forn(sg, 2)dp[i][pos][sg] = INF;dp[0][0][0] = dp[0][0][1] = -INF;forn(i, n - 1) forn(pos, 2) forn(sg, 2) if (dp[i][pos][sg] != INF) {forn(nsg, 2) {int x = sg ? -p[i] : p[i];int y = dp[i][pos][sg];if (pos) swap(x, y);int z = nsg ? -p[i + 1] : p[i + 1];if (z > x) {if (dp[i + 1][0][nsg] > y) {dp[i + 1][0][nsg] = y;pr[i + 1][0][nsg] = make_pair(pos, sg);}} else if (z > y)  {if (dp[i + 1][1][nsg] > x) {dp[i + 1][1][nsg] = x;pr[i + 1][1][nsg] = make_pair(pos, sg);}}}}int pos = -1, sg = -1;forn(j, 2) forn(k, 2) if (dp[n - 1][j][k] != INF) pos = j, sg = k;if (pos == -1) {puts("NO");return;}for (int i = n - 1; i >= 0; i--) {a[i] = sg ? -p[i] : p[i];tie(pos, sg) = pr[i][pos][sg];}puts("YES");forn(i, n) printf("%d ", a[i]);puts("");
}int main() {int t;scanf("%d", &t);while (t--) solve();
}

//std2
#include <bits/stdc++.h>using namespace std;#define forn(i, n) for (int i = 0; i < int(n); ++i)const int INF = 1e9;
const int N = 1000 * 1000 + 13;int n;
int p[N], a[N];
int dp[N][2], pr[N][2];void solve() {scanf("%d", &n);forn(i, n) scanf("%d", &p[i]);forn(i, n) forn(j, 2) dp[i][j] = INF;dp[0][0] = dp[0][1] = -INF;forn(i, n - 1) forn(j, 2) if (dp[i][j] != INF) {int x = j ? -p[i] : p[i];int y = dp[i][j];if (x < y) swap(x, y);forn(nj, 2) {int z = nj ? -p[i + 1] : p[i + 1];if (z > x) {if (dp[i + 1][nj] > y) {dp[i + 1][nj] = y;pr[i + 1][nj] = j;}} else if (z > y)  {if (dp[i + 1][nj] > x) {dp[i + 1][nj] = x;pr[i + 1][nj] = j;}}}}int j = -1;forn(i, 2) if (dp[n - 1][i] != INF) j = i;if (j == -1) {puts("NO");return;}for (int i = n - 1; i >= 0; i--) {a[i] = j ? -p[i] : p[i];j = pr[i][j];}puts("YES");forn(i, n) printf("%d ", a[i]);puts("");
}int main() {int t;scanf("%d", &t);while (t--) solve();
}

G. Subsequences Galore（待补）

题解

//std
#include<bits/stdc++.h>using namespace std;const int N = 23;
const int A = 26;
const int S = 20043;
int n;
string inp[N];
char buf[S];
int cnt[N][A];
const int MOD = 998244353;int add(int x, int y)
{x += y;while(x >= MOD) x -= MOD;while(x < 0) x += MOD;return x;
}int sub(int x, int y)
{return add(x, -y);
}int mul(int x, int y)
{return (x * 1ll * y) % MOD;
}void flip_all(vector<int>& a)
{int msk = (1 << n) - 1;for(int i = 0; i < (1 << (n - 1)); i++)swap(a[i], a[i ^ msk]);
}int val[S];
int* where[S];
int cur = 0;void change(int& x, int y)
{where[cur] = &x;val[cur] = x;x = y;cur++;
}void rollback()
{--cur;(*where[cur]) = val[cur];
}void zeta_transform(vector<int>& a)
{for(int i = 0; i < n; i++){for(int j = 0; j < (1 << n); j++)if((j & (1 << i)) == 0)a[j ^ (1 << i)] = add(a[j ^ (1 << i)], a[j]);}
}                     void mobius_transform(vector<int>& a)
{for(int i = n - 1; i >= 0; i--){for(int j = (1 << n) - 1; j >= 0; j--)if((j & (1 << i)) != 0)a[j] = sub(a[j], a[j ^ (1 << i)]);}
}int cur_max[A];
vector<int> mask_cnt;void rec(int depth, int mask)
{if(depth == n){mask_cnt[mask] = 1;for(int i = 0; i < A; i++)mask_cnt[mask] = mul(mask_cnt[mask], cur_max[i] + 1);}else{int state = cur;for(int i = 0; i < A; i++)change(cur_max[i], min(cur_max[i], cnt[depth][i]));rec(depth + 1, mask + (1 << depth));while(state != cur) rollback();rec(depth + 1, mask);}   
}int main()
{scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%s", buf);inp[i] = buf;for(auto x : inp[i])cnt[i][x - 'a']++;}for(int i = 0; i < A; i++)cur_max[i] = S;mask_cnt.resize(1 << n);rec(0, 0);flip_all(mask_cnt);mobius_transform(mask_cnt);flip_all(mask_cnt);int sum = 0;for(int i = 0; i < (1 << n); i++) sum = add(sum, mask_cnt[i]);zeta_transform(mask_cnt);vector<int> res(1 << n);for(int i = 0; i < (1 << n); i++)res[i] = sub(sum, mask_cnt[((1 << n) - 1) ^ i]);long long ans = 0;for(int i = 0; i < (1 << n); i++){int c = 0, s = 0;for(int j = 0; j < n; j++){if(i & (1 << j)){c++;s += j + 1;}   }ans ^= res[i] * 1ll * c * 1ll * s;}//for(int i = 0; i < (1 << n); i++) printf("%d\n", res[i]);printf("%lld\n", ans);
}