A. Grade Allocation
签到。
Code
/*
* Author: heyuhhh
* Created Time: 2020/3/4 23:31:30
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '
'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e3 + 5;
int n, m;
int a[N];
void run() {
cin >> n >> m;
int sum = 0;
for(int i = 1; i <= n; i++) {
cin >> a[i];
if(i > 1) sum += a[i];
}
cout << min(m, a[1] + sum) << '
';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
int T; cin >> T;
while(T--) run();
return 0;
}
B. String Modification
暴力即可。
枚举后缀，并且根据后缀的长度翻转前缀，最后取字典序最小即可。
Code
/*
* Author: heyuhhh
* Created Time: 2020/3/4 23:22:56
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '
'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 5000 + 5;
int n;
string s;
void run() {
cin >> n >> s;
pair <string, int> ans(s, 1);
for(int i = n - 1; i >= 0; i--) {
string S = s.substr(i);
int len = n - i;
string T = s.substr(0, i);
if(len & 1) reverse(all(T));
string res = S + T;
if(res <= ans.fi) {
ans = MP(res, i + 1);
}
}
cout << ans.fi << '
' << ans.se << '
';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
int T; cin >> T;
while(T--) run();
return 0;
}
C. Primitive Primes
题意：
给出两个多项式：(displaystyle f(x)=a_0+a_1x+cdots+a_{n-1}x^{n-1},g(x)=b_0+b_1x+cdots+b_{n-1}x^{n-1})及一个素数(p)。
先有(h(x)=f(x)cdot g(x)=c_0+c_1+cdots+c_{n+m-2}x^{n+m-2})。
要求输出任意一项(i)，满足(p
ot {|} c_i)，即(p)不整除(c_i)。
题目保证肯定有解。
思路：
- 易发现(f(x),g(x))这两个多项式都至少存在一个系数，满足不被(p)整除。
- 找到最小不被(p)整除的系数(a_i,b_j)，那么答案即为(i+j)。
简要证明一下：(c_{i+j}=a_0b_y+a_1b_{y-1}+cdots+a_ib_j+cdots a_{x}b_{0})。那么前半部分因为有(a_0,a_1,cdots,a_{i-1})，后半部分有(b_0,b_1,cdots,b_{j-1})。所以除开(a_ib_j)这一项，其余都被(p)整除，而容易发现(a_ib_j)不被(p)整除。故答案即为(i+j)这一项的系数。
Code
/*
* Author: heyuhhh
* Created Time: 2020/3/4 23:03:37
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '
'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e6 + 5;
int n, m, p;
int a[N], b[N];
void run() {
cin >> n >> m >> p;
int p1 = -1, p2 = -1;
for(int i = 0; i < n; i++) {
cin >> a[i], a[i] %= p;
if(a[i] && p1 == -1) p1 = i;
}
for(int i = 0; i < m; i++) {
cin >> b[i], b[i] %= p;
if(b[i] && p2 == -1) p2 = i;
}
cout << p1 + p2 << '
';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
run();
return 0;
}
D. Nash Matrix
构造题。
- 我们先找到所有的(X)的位置。
- 枚举每个(X)，从(X)出发确定每个终点位于当前(X)位置的格子。
- 剩下的所有格子都在走一个循环，我们可以按照如下想法构造：
- 不前往已经确定了的格子，这样就会有一个终点；
- 不走出边界，这是非法走法。
最后的构造方法保证了剩下的格子一定走不到终点，那么就是互相循环。
注意一下不合法情况的判断。
细节见代码：
Code
/*
* Author: heyuhhh
* Created Time: 2020/3/5 8:32:12
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '
'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e3 + 5;
int n;
int mp[N][N];
int x[N][N], y[N][N];
const int dx[] = {0, -1, 1, 0, 0}, dy[] = {0, 0, 0, -1, 1};
bool vis[N][N];
void go(int sx, int sy, int px, int py, int dir) {
int nx = px + dx[dir], ny = py + dy[dir];
if(nx < 1 || nx > n || ny < 1 || ny > n || vis[nx][ny]) return;
if(x[nx][ny] != sx || y[nx][ny] != sy) return;
vis[nx][ny] = true;
if(dir == 1) mp[nx][ny] = 2;
else if(dir == 2) mp[nx][ny] = 1;
else if(dir == 3) mp[nx][ny] = 4;
else mp[nx][ny] = 3;
for(int i = 1; i <= 4; i++) go(sx, sy, nx, ny, i);
}
void run() {
cin >> n;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
cin >> x[i][j] >> y[i][j];
if(x[i][j] == i && y[i][j] == j) {
mp[i][j] = 5;
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(mp[i][j] == 5) {
vis[i][j] = true;
for(int k = 1; k <= 4; k++) go(i, j, i, j, k);
}
}
}
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= n; j++) {
if(!mp[i][j]) {
if(x[i][j] != -1 || y[i][j] != -1) {
cout << "INVALID" << '
';
return;
}
bool f = false;
for(int k = 1; k <= 4; k++) {
int nx = i + dx[k], ny = j + dy[k];
if(nx < 1 || nx > n || ny < 1 || ny > n || vis[nx][ny]) continue;
f = true;
mp[i][j] = k;
break;
}
if(f == false) {
cout << "INVALID" << '
';
return;
}
}
}
}
cout << "VALID" << '
';
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(mp[i][j] == 1) cout << "U";
if(mp[i][j] == 2) cout << "D";
if(mp[i][j] == 3) cout << "L";
if(mp[i][j] == 4) cout << "R";
if(mp[i][j] == 5) cout << "X";
}
cout << '
';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
run();
return 0;
}
E. Team Building
题意：
现在有(n)个人，要从中选取(p+k,pleq 7)个人。其中，要选出(p)个人组成一支球队，每支球队中有(p)个位置，每个人在不同的位置有不同的效用(s_{i,j})。
并且还要选出(k)个观众，每个观众的效用为(a_i)。
现在问最后整场比赛的最高效用为多少。
思路：
首先这个题肯定往(dp)方面想，直接暴力的(dp)很好想，但显然时间复杂度不能承受。
注意一个观察：
- 考虑到如果我们选出了(p)个人，那么剩下选择观众时，我们肯定贪心来选择。
- 所以最后选择观众的状态一定为连续的，如果除开参赛选手的话。
我们一开始暴力的(dp)定义为(dp_{i,j,sta})：考虑了前(i)个人，选了(j)个作为观众，当前参赛队员的状态为(sta)的最大效用。
根据上面的观察，我们可以将所有人按照(a_i)降序排序，将(dp)状态重新定义为(dp_{i,sta})表示前(i)个人，当前参赛队员的状态为(sta)，且已经选择了(k)个观众的最大效用。
那么考虑到观众的连续性，在转移时直接计算贪心观众的效用即可。
细节见代码：
Code
/*
* Author: heyuhhh
* Created Time: 2020/3/5 0:03:03
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '
'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5, M = 7;
int n, p, k;
ll dp[N][1 << M];
int s[N][M];
struct people {
int s[7];
int v;
bool operator < (const people &A) const {
return v > A.v;
}
}a[N];
void run() {
for(int i = 1; i <= n; i++) cin >> a[i].v;
for(int i = 1; i <= n; i++) {
for(int j = 0; j < p; j++) {
cin >> a[i].s[j];
}
}
sort(a + 1, a + n + 1);
auto calc = [&](int cur, int c) {
if(k + c < cur) return 0;
return a[k + c + 1].v - a[cur].v;
};
memset(dp, -INF, sizeof(dp));
dp[0][0] = 0;
for(int i = 1; i <= k; i++) dp[0][0] += a[i].v;
for(int i = 1; i <= n; i++) {
for(int sta = 0; sta < 1 << p; sta++) {
dp[i][sta] = dp[i - 1][sta];
int c = 0;
for(int j = 0; j < p; j++) if(sta >> j & 1) ++c;
for(int j = 0; j < p; j++) if(sta >> j & 1) {
dp[i][sta] = max(dp[i][sta], dp[i - 1][sta ^ (1 << j)] + a[i].s[j] + calc(i, c - 1));
}
}
}
cout << dp[n][(1 << p) - 1] << '
';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
while(cin >> n >> p >> k) run();
return 0;
}