Codeforces Round 1012 (Div. 2)

A. Treasure Hunt

注意深度是a.5米。

#include <bits/stdc++.h>
#define x first
#define y second
#define int long longusing namespace std;
typedef unsigned long long ULL ;
typedef pair<int,int> PII ;
typedef pair<long double,long double> PDD ;
const int N = 5010 , M = N * 2 , mod = 998244353 ;
int x , y , a ;void solve()
{cin >> x >> y >> a ;double u = a % (x + y) + 0.5 ;if(u > x) cout << "Yes\n" ;else cout << "No\n" ;
}
signed main()
{std::ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0) ;int t = 1 ;cin >> t ;while (t --) solve() ;return 0;
}

B. Pushing Balls

如果某行或者某列是合法的，那么一定是从这行这列开始连着的1。

#include <bits/stdc++.h>
#define x first
#define y second
#define int long longusing namespace std;
typedef unsigned long long ULL ;
typedef pair<int,int> PII ;
typedef pair<long double,long double> PDD ;
const int N = 5010 , M = N * 2 , mod = 998244353 ;
int n , m ;
char a[55][55] ;
bool st[55][55] ;void solve()
{cin >> n >> m ;for(int i = 0 ; i < n ; i ++)cin >> a[i] ;memset(st , 0 , sizeof st) ;for(int i = 0 ; i < n ; i ++)if(a[i][0] == '1') {for(int j = 0 ; j < m ; j ++) {if(a[i][j] == '1') st[i][j] = 1 ;else break;}}for(int j = 0 ; j < m ; j ++)if(a[0][j] == '1') {for(int i = 0 ; i < n ; i ++) {if(a[i][j] == '1') st[i][j] = 1 ;else break;}}for(int i = 0 ; i < n ; i ++)for(int j = 0 ; j < m ; j ++)if(a[i][j] == '1' && !st[i][j]){cout << "NO\n" ;return;}cout << "YES\n" ;
}
signed main()
{std::ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0) ;int t = 1 ;cin >> t ;while (t --) solve() ;return 0;
}

C. Dining Hall

a[i]==1时，这个人要选最近的没人坐的桌子，a[i]==0时，这个人要选最近的没人坐的椅子。

n最大为50000，也就是最多会坐50000个桌子。直接用BFS，维护桌子和椅子两个set。

#include <bits/stdc++.h>
#define x first
#define y second
#define int long longusing namespace std;
typedef unsigned long long ULL ;
typedef pair<int,int> PII ;
typedef pair<long double,long double> PDD ;
const int N = 50010 , M = N * 2 , mod = 998244353 ;
int n ;
int a[N] ;
int dx[4] = {0 , 0 , 1 , -1} , dy[4] = {-1 , 1 , 0 , 0};
struct node {int x  , y , d ;bool operator<(const node& o) const {if (d != o.d) return d > o.d;if (x != o.x) return x > o.x;return y > o.y;}
};void solve()
{cin >> n ;for(int i = 1 ; i <= n ; i ++) cin >> a[i] ;set<PII> st , used , u , v ;priority_queue<node> pu , pv;queue<node> q ;q.push({0 , 0 , 0}) ;while (q.size()) {auto t = q.front() ;q.pop() ;if(pu.size() >= n && pv.size() >= n) break;if(t.x % 3 && t.y % 3) {st.insert({t.x , t.y}) ;pv.push({t.x , t.y , t.d}) ;int ux = t.x / 3 , uy = t.y / 3 ;if(!used.count({ux , uy})) {used.insert({ux , uy}) ;pu.push({ux , uy , t.d}) ;}continue;}for(int i = 0 ; i < 4 ; i ++) {int fx = t.x + dx[i] , fy = t.y + dy[i] ;if(fx >= 0 && fy >= 0 && !st.count({fx , fy})) {q.push({fx , fy , t.d + 1}) ;st.insert({fx , fy}) ;}}}for(int i = 1 ; i <= n ; i ++) {if(a[i] == 0) {while (u.count({pu.top().x , pu.top().y})) pu.pop() ;auto t = pu.top() ;pu.pop() ;u.insert({t.x , t.y}) ;t.x *= 3 , t.y *= 3 ;cout << t.x + 1 << " " << t.y + 1 << "\n" ;v.insert({t.x + 1 , t.y + 1}) ;}else {while (v.count({pv.top().x , pv.top().y})) pv.pop() ;auto t = pv.top() ;pv.pop() ;v.insert({t.x , t.y}) ;cout << t.x << " " << t.y << "\n" ;u.insert({t.x / 3 , t.y / 3}) ;}}
}
signed main()
{std::ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0) ;int t = 1 ;cin >> t ;while (t --) solve() ;return 0;
}

D. Simple Permutation

感觉这道题需要对脑电波，一开始猜的是“2 1 3 4 5 6 7...”，写了对拍到50都没有问题就交了。最后发现wa8。然后越想越不对，然后发现规律好像是"x , x - 1 , x + 1 , x + 2 , x + 3..."，为了凑尽可能多对，x选择最接近n/2的质数。原理....等我找到了再补。

#include <bits/stdc++.h>
#define x first
#define y second
#define int long longusing namespace std;
typedef unsigned long long ULL ;
typedef pair<int,int> PII ;
typedef pair<long double,long double> PDD ;
const int N = 100010 , M = N * 2 , mod = 998244353 ;
int n ;
int p[N] , cnt , st[N] ;
bool used[N] ;void init() {for(int i = 2 ; i <= N - 10 ; i ++) {if(!st[i]) p[cnt ++] = i ;for(int j = 0 ; p[j] * i <= N - 10 ; j ++) {st[p[j] * i] = 1 ;if(i % p[j] == 0) break;}}
}
void solve()
{cin >> n ;for(int i = 1 ; i <= n ; i ++) used[i] = 0 ;int x = 2 ;for(int i = 0 ; i < cnt ; i ++){if(abs(p[i] - n / 2) < abs(x - n / 2))x = p[i] ;}vector<int> res ;res.push_back(x) ;used[x] = 1 ;for(int i = 1 ; i <= n / 2 ; i ++) {if(x - i >= 1) {res.push_back(x - i) ;used[x - i] = 1 ;}if(x + i <= n) {res.push_back(x + i) ;used[x + i] = 1 ;}}for(int i = 1 ; i <= n ; i ++) if(!used[i])res.push_back(i) ;for(int i = 0 ; i < res.size() ; i ++)cout << res[i] << " " ;cout << "\n" ;
}
signed main()
{std::ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0) ;int t = 1 ;init() ;cin >> t ;while (t --) solve() ;return 0;
}