A. Best Player
模拟。
题意是分别站在 \(X,Y,Z\) 轴上看另外两维构成的点,谁看到的更多。
分别对三维维护一个 \(\text{pair}\) 去重比较即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ll long long
const int N=5003;
#define int long long
int id=0;
void solve() {int n;cin >> n;set<array<int,2>>stx,sty,stz;int ans = 0;char res;for (int i = 0; i < n; ++i) {int x, y, z;cin >> x >> y >> z;stx.insert({y,z});sty.insert({x,z});stz.insert({x,y});}if(stx.size()>ans){ans=stx.size();res='X';}if(sty.size()>ans){ans=sty.size();res='Y';}if(stz.size()>ans){ans=stz.size();res='Z';}cout << res << endl;}
signed main() {ios::sync_with_stdio(false), cin.tie(0);int t = 1;
// cin >> t;while (t--) {solve();}return 0;
}
B. The Great Wall
dp。
设 \(dp_{i,j,0/1/2/3}\) 表示第 \(i\) 个数被分到 \(j\) 组,且 未确定最大最小值 / 已确定最小值 / 已确定最大值 / 已确定最大最小值 的最大答案。
那么当 \(a_i\) 不产生贡献 / 作为最小值 / 作为最大值 时有转移方程为:
\[dp_{i,j,0} = dp_{i,j-1,3}\\
dp_{i,j,1} = \max(dp_{i-1,j,1},dp_{i-1,j-1,3}-a_i,dp_{i-1,j,0}-a_i)\\
dp_{i,j,2} = \max(dp_{i-1,j,2},dp_{i-1,j-1,3}+a_i,dp_{i-1,j,0}+a_i)\\
dp_{i,j,3} = \max(dp_{i-1,j,3},dp_{i-1,j-1,3},dp_{i-1,j-1,1}+a_i,dp_{i-1,j,2}-a_i)\\
\]
\(4\times 10^8\) 的空间存不下,需要滚动。
点击查看代码
#include <bits/stdc++.h>using namespace std;using i64 = long long;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<int> a(n + 1);for(int i = 1; i <= n; i += 1) {cin >> a[i];}const i64 inf = -1E9;vector<array<i64,4>> dp(n + 1, {inf, inf, inf, inf});auto ndp = dp;dp[0][3] = 0;for(int i = 1; i <= n; i += 1) {for(int j = 1; j <= i; j += 1) {ndp[j][0] = dp[j - 1][3];ndp[j][1] = max({dp[j][1], dp[j - 1][3] - a[i], dp[j][0] - a[i]});ndp[j][2] = max({dp[j][2], dp[j - 1][3] + a[i], dp[j][0] + a[i]});ndp[j][3] = max({dp[j][3], dp[j - 1][3], dp[j][1] + a[i], dp[j][2] - a[i]});}swap(dp, ndp);}for(int i = 1; i <= n; i += 1) {cout << dp[i][3] << "\n";}return 0;
}
E. Isomerism
模拟。
读懂题就会做了,直接看代码即可。
点击查看代码
#include <bits/stdc++.h>using namespace std;using i64 = long long;void solve() {map<string,int> mp;mp["-F"] = 8, mp["-Cl"] = 7, mp["-Br"] = 6, mp["-I"] = 5;mp["-CH3"] = 4, mp["-CH2CH3"] = 3, mp["-CH2CH2CH3"] = 2, mp["-H"] = 1;string R[4];cin >> R[0] >> R[1] >> R[2] >> R[3];if(R[0] == R[2] || R[1] == R[3]){cout << "None\n";return;}if(R[0] == R[1] || R[2] == R[3]){cout << "Cis\n";return;}if(R[0] == R[3] || R[2] == R[1]){cout << "Trans\n";return;}if(mp[R[0]] > mp[R[2]] && mp[R[1]] > mp[R[3]] || mp[R[0]] < mp[R[2]] && mp[R[1]] < mp[R[3]]){cout << "Zasamman\n";return;}cout << "Entgegen\n";}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}return 0;
}
G. Photograph
解法一:链表。
模拟一个 \(1\sim n\) 的链表,每次按顺序加进来一个数反过来看就是每次从链表中删掉一个数,删掉这个数后左右两边的指针更新一下即可,先算出总的贡献,删掉数后再减掉那个数的贡献就能得到当前序列的贡献。
点击查看代码
#include <bits/stdc++.h>using namespace std;using i64 = long long;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, q;cin >> n >> q;vector<int> a(n + 1);for(int i = 1;i <= n;i += 1){cin >> a[i];}vector<int> p(n + 1);for(int i = 1;i <= n;i += 1){cin >> p[i];}i64 ans = 0;auto query = [&]()->void{i64 sum = 0;vector<int> l(n + 1, -1), r(n + 1, -1);for(int i = 2;i <= n;i += 1){l[i] = i - 1;r[i - 1] = i;sum += (a[i] - a[i - 1]) * (a[i] - a[i - 1]);}ans = sum; for(int x = n; x >= 1; x -= 1){int i = p[x];int u = l[i], v = r[i];if(u != -1){sum -= (a[i] - a[u]) * (a[i] - a[u]);r[u] = v;}if(v != -1){sum -= (a[i] - a[v]) * (a[i] - a[v]);l[v] = u;}if(u != -1 && v != -1){sum += (a[u] - a[v]) * (a[u] - a[v]);}ans += sum;}cout << ans << "\n";};query();while(q--){int k;cin >> k;k = (k + ans) % n;rotate(p.begin() + 1, p.begin() + k + 1, p.end());query();}return 0;
}
解法二:魔改树状数组(?)
队友写得魔改树状数组,正着按顺序模拟,qoj 冲过去了。
点击查看代码
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ll long long
#define PII pair<int,int>
#define PIII pair<PII,PII>
const int N = 2e5+10;int n,Q;
int a[N];
int cl[N],cr[N];
int lowbit(int x){return x&(-x);
}
void addl(int x,int v){for(int i=x;i<=n;i+=lowbit(i)){cl[i]+=v;}
}void addl(int l,int r,int v){if(r<l)return;addl(l,v);addl(r+1,-v);
}
int getl(int x){int ans=0;for(int i=x;i>=1;i-=lowbit(i)){ans+=cl[i];}return ans;
}
void addr(int x,int v){for(int i=x;i<=n;i+=lowbit(i)){cr[i]+=v;}
}
void addr(int l,int r,int v){if(r<l)return;addr(l,v);addr(r+1,-v);
}
int getr(int x){int ans=0;for(int i=x;i>=1;i-=lowbit(i)){ans+=cr[i];}return ans;
}
deque<int> b;
void solve() {cin >> n>>Q;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){int x;cin>>x;b.push_back(x);cl[i]=cr[i]=0;}ll ans=0,s=0;for(int i=0;i<n;i++){int l=getl(b[i]),r=getr(b[i]);if(!l&&!r){addr(1,b[i]-1,b[i]);addl(b[i]+1,n,b[i]);}else if(l&&r){addr(l+1,b[i]-1,-r);addr(l+1,b[i]-1,b[i]);addl(b[i]+1,r-1,-l);addl(b[i]+1,r-1,b[i]);ans-=(a[r]-a[l])*(a[r]-a[l]);ans+=(a[r]-a[b[i]])*(a[r]-a[b[i]]);ans+=(a[l]-a[b[i]])*(a[l]-a[b[i]]);}else if(l){addl(b[i]+1,n,-l);addl(b[i]+1,n,b[i]);addr(l+1,b[i]-1,b[i]);ans+=(a[l]-a[b[i]])*(a[l]-a[b[i]]);}else{addr(1,b[i]-1,-r);addr(1,b[i]-1,b[i]);addl(b[i]+1,r,b[i]);ans+=(a[r]-a[b[i]])*(a[r]-a[b[i]]);}s+=ans;}cout<<s<<endl;a[0]=-1;for(int o=1;o<=Q;o++){ll p;cin>>p;p+=s;p%=n;s=0;ans=0;for(int i=0;i<p;i++){b.push_back(b.front());b.pop_front();}for(int i=1;i<=n;i++){cl[i]=cr[i]=0;}for(int i=0;i<n;i++){int l=getl(b[i]),r=getr(b[i]);if(!l&&!r){addr(1,b[i]-1,b[i]);addl(b[i]+1,n,b[i]);}else if(l&&r){addr(l+1,b[i]-1,-r);addr(l+1,b[i]-1,b[i]);addl(b[i]+1,r-1,-l);addl(b[i]+1,r-1,b[i]);ans-=(a[r]-a[l])*(a[r]-a[l]);ans+=(a[r]-a[b[i]])*(a[r]-a[b[i]]);ans+=(a[l]-a[b[i]])*(a[l]-a[b[i]]);}else if(l){addl(b[i]+1,n,-l);addl(b[i]+1,n,b[i]);addr(l+1,b[i]-1,b[i]);ans+=(a[l]-a[b[i]])*(a[l]-a[b[i]]);}else{addr(1,b[i]-1,-r);addr(1,b[i]-1,b[i]);addl(b[i]+1,r,b[i]);ans+=(a[r]-a[b[i]])*(a[r]-a[b[i]]);}s+=ans;}cout<<s<<endl;}
}
signed main() {ios::sync_with_stdio(false), cin.tie(0);int t = 1;
// cin >> t;while (t--) {solve();}return 0;
}
J. Let's Play Jigsaw Puzzles!
没读,貌似构造。
点击查看代码
//#pragma GCC optimize(1)
//#pragma GCC optimize(2)
//#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define endl '\n'
#define ll long long
#define PII pair<int,int>
#define PIII pair<PII,PII>
const int N = 5003;
int m;
int a[N][N];
void solve() {cin >> m;if (m == 1) {int x, y, z, w;cin >> x >> y >> z >> w;cout << 1 << endl;return;}vector<PIII>stn; //上左下右map<int, int>q[3];for (int i = 1; i <= m * m; i++) {int x, y, z, w;cin >> x >> y >> z >> w;stn.push_back({{x, z}, {y, w}});if (x != -1)q[0][x]++;if (z != -1)q[1][z]++;q[2][x]++;q[2][y]++;q[2][z]++;q[2][w]++;}sort(stn.begin(),stn.end());for (auto [x, y] : q[2]) {if (y == 2) {if (q[1][x] == 1&&q[0][x]==1) {a[1][1] = x;break;}}}for (int i = 1; i <= m; i++) {a[0][i] = a[i][0] = -1;}for (int i = 1; i <= m; i++) {for (int j = 1; j <= m; j++) {auto[u,v] = *lower_bound(stn.begin(),stn.end(),PIII{{a[i - 1][j], a[i][j - 1]}, {-1, -1}});auto [x,z]=u;auto [y,w]=v;a[i + 1][j] = y;a[i][j + 1] = w;}}for (int i = 1; i <= m; i++) {for (int j = 1; j <= m; j++) {cout << a[i][j] << " \n"[j == m];}}
}
signed main() {
// freopen("in.txt", "r", stdin); ios::sync_with_stdio(false), cin.tie(0);int t = 1;
// cin >> t;while (t--) {solve();}return 0;
}
K. Browser Games
字典树。
字典树上再维护一个每个节点的数量,先将全部字符串加入,后续遍历每个字符串,每新加一个,就从字典树上减去它的计数,然后判断能不能与先前的取的前缀合并掉。
点击查看代码
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define endl '\n'
#define ll long long
#define PII pair<int,int>
#define PIII pair<PII,PII>
const int N = 3e6+10;int tr[N][28], cnt = 1;
int a[N], vis[N];
int f(char x) {if (x == '.')return 26;if (x == '/')return 27;return x - 'a';
}
vector<int>q;
int ans=0;
void insert(string s, int v) {int len = s.length(), p = 1;for (int i = 0; i < len; i++) {int c = f(s[i]);if (tr[p][c] == 0)tr[p][c] = ++cnt;p = tr[p][c];if(v==-1)q.push_back(p);a[p] += v;}if(v==-1){if(!a[p]){vis[p]=1;ans++;}}if (v == -1) {for (int i = q.size()-1; i >=0; i--) {auto p=q[i];if(!a[p]){int f=0;for(int j=0;j<28;j++){if(tr[p][j]&&vis[tr[p][j]])f=1,vis[tr[p][j]]=0,ans--;}if(f){if(vis[p]){}else{vis[p]=1;ans++;}}}else{break;}}q.clear();}
}
int n;
string b[N];
void solve() {cin >> n;a[1] = 1;for (int i = 1; i <= n; i++) {cin >> b[i];insert(b[i], 1);}for (int i = 1; i <= n; i++) {insert(b[i], -1);cout<<ans<<endl;}
}
signed main() {
// freopen("in.txt", "r", stdin);ios::sync_with_stdio(false), cin.tie(0);int t = 1;
// cin >> t;while (t--) {solve();}return 0;
}