好用的网站模板,重新安装 wordpress,网站运营与维护的方法,淘宝数据网站开发2020ICPC银川(A E G J K)
2020ICPC银川
A. Best Player#xff08;模拟#xff09;
在某一维方向上无法区分的点显然另两维坐标相同 #xff0c; 那么在当前维度上能区分的点个数就是本质不同的另两维坐标组成的点对的个数 #xff0c; 用set维护一下即可。
#include模拟
在某一维方向上无法区分的点显然另两维坐标相同 那么在当前维度上能区分的点个数就是本质不同的另两维坐标组成的点对的个数 用set维护一下即可。
#includebits/stdc.h
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int INF 9e18;
const int N 2e6 10;
const int mod 1e9 7;
typedef pairint,intPII;int n;setPII x , y , z;signed main(){cin n;for(int i 1 ; i n ; i ) {int a , b , c;cin a b c;x.insert({b , c});y.insert({a , c});z.insert({a , b});}int res max({x.size() , y.size() , z.size()});if(x.size() res) {cout X;} else if(y.size() res) {cout Y;} else {cout Z;}return 0;
}
//freopen(文件名.in,r,stdin);
//freopen(文件名.out,w,stdout);E. Isomerism模拟
根据题意模拟一下即可
#includebits/stdc.h
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int INF 9e18;
const int N 2e6 10;
const int mod 1e9 7;
typedef pairint,intPII;mapstring , intmp;
string s[5];
int t;signed main(){mp[-F] 8;mp[-Cl] 7;mp[-Br] 6;mp[-I] 5;mp[-CH3] 4;mp[-CH2CH3] 3;mp[-CH2CH2CH3] 2;mp[-H] 1;cin t;while(t --) {for(int i 1 ; i 4; i ){cin s[i];}if(s[1] s[3] || s[2] s[4]) {cout None\n;} else if(s[1] s[2] || s[3] s[4]) {cout Cis\n;} else if(s[1] s[4] || s[2] s[3]) {cout Trans\n;} else {int tag1 0 , tag2 0;if(max(mp[s[1]] , mp[s[3]]) mp[s[1]]) tag1 1;else tag1 2;if(max(mp[s[2]] , mp[s[4]]) mp[s[2]]) tag2 1;else tag2 2;if(tag1 tag2) {cout Zasamman\n;} else {cout Entgegen\n;}} }return 0;
}
//freopen(文件名.in,r,stdin);
//freopen(文件名.out,w,stdout);G. Photograph(链表 模拟)
观察操作 我们不难想到用链表模拟插入操作 然后边插入边计算贡献 但是这样需要维护插入的位置 复杂度 nqlogn 显然不能接受 考虑逆过程 即删除操作 删除操作并不需要维护插入位置 边删除边计数 复杂度 nq 直接模拟即可。
#includebits/stdc.h
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int INF 9e18;
const int N 1e5 10;
const int mod 1e9 7;
typedef pairint,intPII;int n , q;
int cnt[N] , h[N] , pos[N];
int nex_num(int x){ return (x 1) % n; }
int cal(int x){ return x * x; }
int need[N];signed main(){cin n q;for(int i 0 ; i n ; i ) cin h[i];for(int i 0 ; i n ; i ) cin pos[i] , pos[i] - 1;vectorint pre(n 2) , nex(n 2) , pree(n 2) , nexx(n 2);/*n ... 1 - n - 1 ... n 1*/pre[0] n;//[0 - n - 1] -1 nnex[n] 0;nex[n - 1] n 1;pre[n 1] n - 1;for(int i 1 ; i n - 1 ; i ) {pre[i] i - 1;nex[i - 1] i;}for(int i 2 ; i q 1 ; i ) cin cnt[i];int prex 0 , lans 0;for(int i 1 ; i q 1 ; i ) {int now (prex lans cnt[i]) % n;prex now;for(int j now , cnt 1 ; cnt n ; j nex_num(j) , cnt 1) {need[cnt] pos[j];}pree pre;nexx nex;int res 0 , ans 0;for(int j 1 ; j n ; j ) res cal(h[j] - h[j - 1]);for(int j n ; j 1 ; j --) {ans res;int now need[j];if(pree[now] ! n) res - cal(h[now] - h[pree[now]]);if(nexx[now] ! n 1) res - cal(h[now] - h[nexx[now]]);if(pree[now] ! n nexx[now] ! n 1) res cal(h[pree[now]] - h[nexx[now]]);nexx[pree[now]] nexx[now];pree[nexx[now]] pree[now];}cout ans \n;lans ans;}return 0;
}
//freopen(文件名.in,r,stdin);
//freopen(文件名.out,w,stdout);J. Let’s Play Jigsaw Puzzles!(二维链表)
根据题意 维护一个二维链表即可。
#includebits/stdc.h
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int INF 9e18;
const int N 2e6 10;
const int mod 1e9 7;
typedef pairint,intPII;int m , l[N] , r[N] , u[N] , d[N];
int a , b , c , dd;
//上 下 左 右signed main(){IOScin m;for(int i 1 ; i m * m ; i ) {cin a b c dd;u[i] a;if(a ! -1) d[a] i;d[i] b;if(b ! -1) u[b] i;l[i] c;if(c ! -1) r[c] i;r[i] dd;if(dd ! -1) l[dd] i;}int pos 0;for(int i 1 ; i m * m ; i ) {if(u[i] -1 l[i] -1) pos i;}for(int i pos ; i ! -1 ; i d[i]) {for(int j i , k 1 ; j ! -1 k m ; j r[j] , k ) {if(k ! m) cout j ;else cout j ;}cout \n;}return 0;
}
//freopen(文件名.in,r,stdin);
//freopen(文件名.out,w,stdout);K. Browser Games字典树
大意对于前 i 个字符串找出一个最小的前缀集使得前 i 个字符串都能在前缀集中找到前缀但是后 n - i 个字符串无法在前缀集中找到前缀 求对于每一个 i 的最小前缀集大小。
思路对于字符串的前缀问题 考虑字典树 我们先建立字典树 然后对于出现的所有前缀全部计数。对于第 i 个前缀 考虑把第 i 个字符串所对应的前缀计数全部删除 那么现在树中的非 0 位置就是不能出现在前缀集中的前缀 0 的位置就是可以出现在前缀集中的前缀 对于所有可以出现在前缀集部分的前缀 用最小的前缀代表即可让前缀集最小 。 最小前缀的位置即删除前缀时遇到的第一个 0 的位置 这时考虑当前节点子树的贡献由原来的 x 变成现在的 1 所以我们需要维护每一个节点所在子树的贡献然后 O1 的实现转移。
#includebits/stdc.h
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//#define int long long
//const int INF 9e18;
const int N 2e6 5e5;
const int mod 1e9 7;
typedef pairint,intPII;
int tree[N][28] , cnt[N] , siz[N] , idx , n , fa[N];
string s;int get(char c) {if(c a c z) return c - a;if(c .) return 26;return 27;
}void insert(string s){int now 0 , n s.size();for(int i 0 ; i n ; i ){int c get(s[i]);if(!tree[now][c]) tree[now][c] idx;fa[tree[now][c]] now;now tree[now][c];//每一个now代表一个从根到当前节点的不同的前缀cnt[now] 1;}
}
void query(string s , int res){bool tag 0;int now 0 , n s.size();for(int i 0 ; i n ; i ){int c get(s[i]);now tree[now][c];cnt[now] - 1;if(!cnt[now] !tag) {res res - siz[now] 1;int val siz[now];while(fa[now]) siz[fa[now]] (1 - val) , now fa[now]; break;}}
}signed main(){IOScin n;vectorstringve;for(int i 1 ; i n ; i ) {cin s;insert(s);ve.push_back(s);}int res 0;for(int i 0 ; i n ; i ) {query(ve[i] , res);cout res \n;}return 0;
}
//freopen(文件名.in,r,stdin);
//freopen(文件名.out,w,stdout);
