一场比较简单的 $\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;
//edge[++ edge_num] = (Edge){from , head[to] , dis}; head[to] = 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