一场比较简单的 $\text{Div} 2$。
A - Ahahahahahahahaha 题目翻译 即给定一个长度为 $n$ $(2 \leq n \leq 10^3)$ 的 $01$ 串，要求至多删去 $\frac{n}{2}$ 个字符，使得剩下的串中奇数位的数之和 = 偶数位之和 ， 要求输出删去后剩下的串。
分析 注意一下 $0$ 与 $1$ 的数量，不难发现总会有一个小于 $\frac{n}{2}$。
则我们将小于 $\frac{n}{2}$ 的那个数字全部删掉即可。
若我们删掉的是数字 $0$ ，则还要注意一下剩下的 $1$ 的个数，若剩下的数目为奇数需要则多删去一个。
时间复杂度 $O(n)$。
Code[Accepted] #include <algorithm> #include <iostream> #include <cstring> #include <iomanip> #include <cstdlib> #include <climits> #include <cstdio> #include <bitset> #include <string> #include <vector> #include <cctype> #include <stack> #include <queue> #include <deque> #include <cmath> #include <map> #include <set> #define I inline #define fi first #define se second #define pb push_back #define MP make_pair #define PII pair<int , int> #define PSL pair<string , long long> #define PLL pair<long long , long long> #define all(x) (x).begin() , (x).end() #define copy(a , b) memcpy(a , b , sizeof(b)) #define clean(a , b) memset(a , b , sizeof(a)) #define rep(i , l , r) for (int i = (l); i <= (r); i ++) #define per(i , r , l) for (int i = (r); i >= (l); i --) #define PE(i , x) for(int i = head[x]; i; i = edge[i].last) #define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl typedef long long ll;typedef unsigned long long ull; template <class T >inline void read (T &x) char c = getchar(), f = 0 ; x = 0 ; while (!isdigit (c)) f = (c == '-' ), c = getchar(); while (isdigit (c)) x = x * 10 + c - '0' , c = getchar(); x = f ? -x : x; } using namespace std ; const int N = 10001 ;const int M = 100001 ;const int HA = 998244353 ; int main () #ifdef LOCAL freopen("try.in" , "r" , stdin ); freopen("try1.out" , "w" , stdout ); #endif int t; read(t); while (t --){ int x , n , cnt[2 ] = {0 , 0 }; read(n); rep(i , 1 , n){ cin >> x; cnt[x] ++; } if (cnt[0 ] >= cnt[1 ]){ cout << n - cnt[1 ] << "\n" ; rep(i , 1 , n - cnt[1 ]){ cout << "0" << " " ; } puts ("" ); } else { if ((n - cnt[0 ]) % 2 == 0 ){ cout << n - cnt[0 ] << "\n" ; rep(i , 1 , n - cnt[0 ]){ cout << "1" << " " ; } puts ("" ); } else { cout << n - cnt[0 ] - 1 << "\n" ; rep(i , 1 , n - cnt[0 ] - 1 ){ cout << "1" << " " ; } puts ("" ); } } } return 0 ; }
B - Big Vova 题目翻译 给定一个长度为 $n (1 \leq n \leq 10^3)$ 的数列，要求对这个数列重新指定顺序，使得这个数列的每一个前缀 $text{gcd} $组成的新序列的字典序最大。
分析 $n$ 很小，直接枚举即可。
时间复杂度 $O(n^2 \log n)$。
Code[Accepted] #include <algorithm> #include <iostream> #include <cstring> #include <iomanip> #include <cstdlib> #include <climits> #include <cstdio> #include <bitset> #include <string> #include <vector> #include <cctype> #include <stack> #include <queue> #include <deque> #include <cmath> #include <map> #include <set> #define I inline #define fi first #define se second #define pb push_back #define MP make_pair #define PII pair<int , int> #define PSL pair<string , long long> #define PLL pair<long long , long long> #define all(x) (x).begin() , (x).end() #define copy(a , b) memcpy(a , b , sizeof(b)) #define clean(a , b) memset(a , b , sizeof(a)) #define rep(i , l , r) for (int i = (l); i <= (r); i ++) #define per(i , r , l) for (int i = (r); i >= (l); i --) #define PE(i , x) for(int i = head[x]; i; i = edge[i].last) #define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl typedef long long ll;typedef unsigned long long ull; template <class T >inline void read (T &x) char c = getchar(), f = 0 ; x = 0 ; while (!isdigit (c)) f = (c == '-' ), c = getchar(); while (isdigit (c)) x = x * 10 + c - '0' , c = getchar(); x = f ? -x : x; } using namespace std ; const int N = 10001 ;const int M = 100001 ;const int HA = 998244353 ; ll a[M] , n , b[M] , ans[M]; ll gcd (ll a , ll b) { return !b ? a : gcd(b , a % b); } bool vis[M]; int main () #ifdef LOCAL freopen("try.in" , "r" , stdin ); freopen("try1.out" , "w" , stdout ); #endif int t; read(t); while (t --){ clean(vis , 0 ) , clean(a , 0 ); read(n); rep(i , 1 , n) read(a[i]); int d = 0 ; rep(i , 1 , n){ int maxn = 0 , pla = 0 ; rep(j , 1 , n){ if (!vis[j] && maxn < gcd(a[j] , d)){ maxn = gcd(a[j] , d); pla = j; } } vis[pla] = 1 ; d = gcd(d , a[pla]); cout << a[pla] << " " ; } puts ("" ); } return 0 ; }
C - Chocolate Bunny 题目翻译 这是一道交互题。
有一个 $n$ 个数的排列，每次询问 $x,y$ 得到 $a_x\bmod a_y$ 的值。
最多询问 $2\times n$ 次，请猜出这个序列。
分析 最多 $2 \times n$ 次的询问限制暗示我们需要询问 $x \bmod y$ 与 $y \bmod x$。
如果 $x > y$，则有
即 $x > y$ 时，满足 $y = y \bmod x$。
如果 $x < y$，则有
即 $x < y$ 时，满足 $x = x \bmod y$。
直接询问即可，询问次数为 $2 \times n - 2$。
Code[Accepted] #include <algorithm> #include <iostream> #include <cstring> #include <iomanip> #include <cstdlib> #include <climits> #include <cstdio> #include <bitset> #include <string> #include <vector> #include <cctype> #include <stack> #include <queue> #include <deque> #include <cmath> #include <map> #include <set> #define I inline #define fi first #define se second #define pb push_back #define MP make_pair #define PII pair<int , int> #define PSL pair<string , long long> #define PLL pair<long long , long long> #define all(x) (x).begin() , (x).end() #define copy(a , b) memcpy(a , b , sizeof(b)) #define clean(a , b) memset(a , b , sizeof(a)) #define rep(i , l , r) for (int i = (l); i <= (r); i ++) #define per(i , r , l) for (int i = (r); i >= (l); i --) #define PE(i , x) for(int i = head[x]; i; i = edge[i].last) #define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl typedef long long ll;typedef unsigned long long ull; template <class T >inline void read (T &x) char c = getchar(), f = 0 ; x = 0 ; while (!isdigit (c)) f = (c == '-' ), c = getchar(); while (isdigit (c)) x = x * 10 + c - '0' , c = getchar(); x = f ? -x : x; } using namespace std ; const int N = 10001 ;const int M = 100001 ;const int HA = 998244353 ; int p[M] , vis[M];int main () #ifdef LOCAL freopen("try.in" , "r" , stdin ); freopen("try1.out" , "w" , stdout ); #endif int n; cin >> n; int j = 0 ; rep(i , 1 , n - 1 ) { cout << "? " << i + 1 << " " << j + 1 << std ::endl ; int x; cin >> x; cout << "? " << j + 1 << " " << i + 1 << std ::endl ; int y; cin >> y; if (x < y) { p[j] = y; vis[y - 1 ] = 1 ; j = i; } else { p[i] = x; vis[x - 1 ] = 1 ; } } p[j] = 1 ; while (vis[p[j] - 1 ]) ++p[j]; cout << "!" ; rep(i , 0 , n - 1 ) cout << " " << p[i]; cout << endl ; return 0 ; }
D - Discrete Centrifugal Jumps 题意翻译 你一开始站在第 $1$ 栋大楼楼顶，需要跳到第 $n (2 \le n \le 3 \times 10^5)$ 栋大楼楼顶。
每次可以向相邻的大楼跳跃，或者说如果中间一整段都比起点和终点都要低或高，就可以直接跳过去。
求 $1$ 到 $n$ 的最小跳跃次数。
分析 先考虑中间一整段都比两端点低的时候怎么做。
设 $f[i]$ 表示从 $1$ 跳到 $i$ 的最少次数，则显然有 $f[i] = f[j] + 1 (h[i] > h[j])$。
那现在问题就成了如何维护 $i$ 号点前面第一个比 $i$ 号点高的点。直接单调栈维护即可。
另一种情况也同理。
时间复杂度 $O(n)$。
Code[Accepted] #include <algorithm> #include <iostream> #include <cstring> #include <iomanip> #include <cstdlib> #include <climits> #include <cstdio> #include <bitset> #include <string> #include <vector> #include <cctype> #include <stack> #include <queue> #include <deque> #include <cmath> #include <map> #include <set> #define I inline #define fi first #define se second #define pb push_back #define MP make_pair #define PII pair<int , int> #define PSL pair<string , long long> #define PLL pair<long long , long long> #define all(x) (x).begin() , (x).end() #define copy(a , b) memcpy(a , b , sizeof(b)) #define clean(a , b) memset(a , b , sizeof(a)) #define rep(i , l , r) for (int i = (l); i <= (r); i ++) #define per(i , r , l) for (int i = (r); i >= (l); i --) #define PE(i , x) for(int i = head[x]; i; i = edge[i].last) #define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl typedef long long ll;typedef unsigned long long ull; template <class T >inline void read (T &x) char c = getchar(), f = 0 ; x = 0 ; while (!isdigit (c)) f = (c == '-' ), c = getchar(); while (isdigit (c)) x = x * 10 + c - '0' , c = getchar(); x = f ? -x : x; } using namespace std ; const int N = 10001 ;const int M = 300010 ;const int HA = 998244353 ; ll f[M] , h[M] , n; ll mx[M] , mn[M]; int main () #ifdef LOCAL freopen("try.in" , "r" , stdin ); freopen("try1.out" , "w" , stdout ); #endif read(n); rep(i , 1 , n){ read(h[i]); } stack <ll> sta; sta.push(0 ); rep(i , 1 , n){ while (h[sta.top()] >= h[i]) sta.pop(); mn[i] = sta.top(); sta.push(i); } stack <ll> sta2; sta2.push(0 ); h[0 ] = 0x3f3f3f3f ; rep(i , 1 , n){ while (h[sta2.top()] <= h[i]) sta2.pop(); mx[i] = sta2.top(); sta2.push(i); } f[1 ] = 0 ; rep(i , 2 , n){ if (h[i] == h[i - 1 ]){ f[i] = f[i - 1 ] + 1 ; } else if (h[i - 1 ] < h[i]){ ll pla = i - 1 ; f[i] = f[i - 1 ] + 1 ; while (pla != 0 ){ f[i] = min(f[i] , f[pla] + 1 ); if (h[pla] >= h[i]) break ; pla = mx[pla]; } } else { ll pla = i - 1 ; f[i] = f[i - 1 ] + 1 ; while (pla != 0 ){ f[i] = min(f[i] , f[pla] + 1 ); if (h[pla] <= h[i]) break ; pla = mn[pla]; } } } printf ("%lld\n" , f[n]); return 0 ; }
E - Egor in the Republic of Dagestan 题意翻译 给出 $n$ 个点 $m$ 条边的有向图，边有黑白两种颜色。
现在要给点染色，每个点染成黑或白，白点只能走它连出的白色边，黑点只能走它连出的黑色边。
求一种染色方案使得 $1\to n$ 的最短路径最长。
分析 题目中能否走这条边取决于这条边起始点的颜色，这很不好处理。
考虑建反图，让能否走这条边就取决于终点的颜色。
之后从 $n$ 号点开始 $\text{bfs}$。
对于点 $i$，在其第一次被枚举到时就证明它在最短路上。为了避免走它，我们将其颜色染为与边的颜色相反的颜色。
若之后再次碰到 $i$，若 $i$ 的颜色与边的颜色相同则进行松弛，并加入队列之中。
这样就最大化了每个点到 $n$ 的距离，也包括 $1$ 到 $n$ 的距离。
至于自始至终没有染色的点证明根本走不到，随便染一下即可。
时间复杂度 $O(n)$。
Code[Accepted] #include <algorithm> #include <iostream> #include <cstring> #include <iomanip> #include <cstdlib> #include <climits> #include <cstdio> #include <bitset> #include <string> #include <vector> #include <cctype> #include <stack> #include <queue> #include <deque> #include <cmath> #include <map> #include <set> #define I inline #define fi first #define se second #define pb push_back #define MP make_pair #define PII pair<int , int> #define PSL pair<string , long long> #define PLL pair<long long , long long> #define all(x) (x).begin() , (x).end() #define copy(a , b) memcpy(a , b , sizeof(b)) #define clean(a , b) memset(a , b , sizeof(a)) #define rep(i , l , r) for (int i = (l); i <= (r); i ++) #define per(i , r , l) for (int i = (r); i >= (l); i --) #define PE(i , x) for(int i = head[x]; i; i = edge[i].last) #define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl typedef long long ll;typedef unsigned long long ull; template <class T >inline void read (T &x) char c = getchar(), f = 0 ; x = 0 ; while (!isdigit (c)) f = (c == '-' ), c = getchar(); while (isdigit (c)) x = x * 10 + c - '0' , c = getchar(); x = f ? -x : x; } using namespace std ; const int N = 10001 ;const int M = 500011 ;const int HA = 998244353 ; int n , m; struct Edge { int to , last , dis; }edge[M << 1 ]; int edge_num;int head[M << 1 ]; I void add_edge (int from , int to , int dis) { edge[++ edge_num] = (Edge){to , head[from] , dis}; head[from] = edge_num; } ll dis[M] , col[M]; void bfs () queue <int > q; clean(dis , -1 ) , clean(col , -1 ); q.push(n); dis[n] = 0 ; while (!q.empty()){ int fro = q.front(); q.pop(); PE(i , fro){ int to = edge[i].to; if (dis[to] != -1 ) continue ; if (col[to] == -1 ) col[to] = (edge[i].dis ^ 1 ); else if (col[to] == edge[i].dis){ dis[to] = dis[fro] + 1 ; q.push(to); } } } } int main () #ifdef LOCAL freopen("try.in" , "r" , stdin ); freopen("try1.out" , "w" , stdout ); #endif read(n) , read(m); rep(i , 1 , m){ int u , v , w; read(u) , read(v) , read(w); add_edge(v , u , w); } bfs(); printf ("%lld\n" , dis[1 ]); rep(i , 1 , n){ printf ("%d" , col[i] == 0 ? 0 : 1 ); } return 0 ; }
THE END 
