A.Grade Allocation
题意：
n个人，每个人有一个成绩，要求最高分不超过m，求在所有人平均分不变的条件下，最高分最高为几分
题解：
总要尽量把分数放在第一个人上面，min(sum(score),m)即可
#include
using namespace std;
const int maxn = 1005;
int a[maxn];
void solve()
{
int n, m;
scanf("%d%d", &n, &m);
int sum = 0;
for (int i = 0, x; i < n; i++)
{
scanf("%d", &x);
sum += x;
}
printf("%d\n", min(sum, m));
}
int main()
{
int t;
for (scanf("%d", &t); t >= 1; t--)
solve();
}B.String Modification
题意：
给定一个长度为n的字符串s。现规定一种操作。规则如下：
选定一个k(1<=k<=n),依次从1开始到n−k+1的下标向后截取长度为k的字符串并将其翻转。问k取多少可以使得操作后的字符串字典序最小。
题解：
如果真的暴力枚举可能会超时，拿样例试一试就可以发现规律：
操作后的字符串前面为原字符串s[k,len]
后面根据后缀（即n-k）分奇偶性进行讨论：
当后缀为奇数时：s[1,k-1]进行翻转
当后缀为偶数时，s[1,k-1]即为后缀
#include
using namespace std;
const int maxn = 1005;
int a[maxn];
void solve()
{
int n;
string s;
cin >> n >> s;
int ans = 1;
string res = s;
for (int k = 1; k < n; k++)
{
string a = s.substr(0, k);
string b = s.substr(k);
if ((n - k) & 1)
reverse(a.begin(), a.end());
b += a;
if (b < res)
{
res = b;
ans = k + 1;
}
}
cout << res << endl
<< ans << endl;
}
int main()
{
int t;
for (scanf("%d", &t); t >= 1; t--)
solve();
}C.Primitive Primes（本原多项式）
题意：
f(x) = a0+a1x+...+anx^(n-1) , g(x) = b0+b1x+...+bnx^(n-1)，h(x) = f(x)*g(x)，问h（x）的哪一项系数模p!=0
题解：
从低位向高位扫描。设多项式A的第一个不能被p整除的项系数为ai，多项式B的第一个不能被p整除的项系数为bj，则最后所得答案为i+j。
证明：若存在其他的数对(x,y)满足x+y=i+j,则x<i或y<j一定有一条成立。那么对所得项系数的贡献一定是p的倍数。而i+j一定不是p的倍数，所以答案一定正确。
看了下题目中定义，与本原多项式很像，同样可以从本原多项式引理的证明中推出：
本原多项式百度百科：https://baike.baidu.com/item/%E6%9C%AC%E5%8E%9F%E5%A4%9A%E9%A1%B9%E5%BC%8F/3246261?fr=aladdin#reference-[2]-1649460-wrap
#include
using namespace std;
const int maxn = 1e6 + 5;
int a[maxn], b[maxn];
int main()
{
int n, m, p;
scanf("%d%d%d", &n, &m, &p);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
for (int i = 0; i < m; i++)
scanf("%d", &b[i]);
int i = 0, j = 0;
while (i < n && a[i] % p == 0)
i++;
while (j < m && b[j] % p == 0)
j++;
printf("%d\n", i + j);
return 0;
}D.Nash Matrix（BFS）
题意：
每个方块上有5个字母（L、R、U、D、X）之一，分别代表在该位置应该向左右上下或停在原地不动。现在给你从每个点出发最终会到达的位置（若最后会在一群点之间反复横跳就给你(−1,−1)）问你是否能够还原每个方块上的字母，若能并还原。
题解：
走到自己位置上的一定是'X'，然后同一路径上的目的地一定一样，可以从每个‘X’开始把同一目的地的都搜过去，处理出来。对于所有(−1,−1)的点向周围扫描其他(−1,−1)的点BFS即可。最后整张图遍历一遍判断有没有没有处理过的点。
#include
using namespace std;
typedef long long ll;
typedef pair pii;
const int maxn = 1005;
pii p[maxn][maxn];
int vis[maxn][maxn];
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int n;
char dirc(int x)
{
if (x == 1)
return 'L';
if (x == 2)
return 'R';
if (x == 3)
return 'U';
if (x == 4)
return 'D';
if (x == 5)
return 'X';
}
int dird(int x)
{
if (x == 0)
return 2;
if (x == 1)
return 1;
if (x == 2)
return 4;
if (x == 3)
return 3;
}
void bfs(int x, int y, bool f)
{
queue q;
q.push({x, y});
while (!q.empty())
{
pii now = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int tx = now.first + dir[i][0], ty = now.second + dir[i][1];
if (vis[tx][ty] || tx n || ty n)
continue;
if (!f)
{
if (p[tx][ty].first == -1 && p[tx][ty].second == -1)
{
vis[tx][ty] = i + 1;
q.push({tx, ty});
}
}
else if (p[tx][ty].first == x && p[tx][ty].second == y)
{
vis[tx][ty] = i + 1;
q.push({tx, ty});
}
}
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%d%d", &p[i][j].first, &p[i][j].second);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (vis[i][j])
continue;
if (p[i][j].first == i && p[i][j].second == j)
{
vis[i][j] = 5;
bfs(i, j, 1);
}
else if (p[i][j].first == -1 && p[i][j].second == -1)
{
for (int k = 0; k < 4; k++)
{
int tx = i + dir[k][0], ty = j + dir[k][1];
if (p[tx][ty].first == -1 && p[tx][ty].second == -1)
{
vis[i][j] = dird(k);
bfs(i, j, 0);
break;
}
}
}
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (vis[i][j] == 0)
{
puts("INVALID");
return 0;
}
puts("VALID");
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
printf("%c", dirc(vis[i][j]));
puts("");
}
return 0;
}E.Team Building（状压dp）
题意：
n个人，要求选择其中p个人作为球员，其中k个人作为观众，ai代表每个人作为观众的能力值, (1<=i<=n,1<=j<=p)代表第i个人作为球员的第j号位置的能力值，求能力值之和的最大值
题解：
观察到p的范围很小，所以考虑状压dp。首先我们按照每个人作为观众的贡献从大到小进行排序。可以得出观众只能在前k+p人中选取。因为如果后面的人作为观众，前面的人至少有1人不被选中，选他作为观众明显为更优解。 表示考虑前i个人选取队员的状态为j时的最优值,只有观众数量还没有满并且排序后编号不大于k+p的时候这个人才能考虑成为观众。然后对于不同的状态全部扫描一遍即可。注意初始要把所有状态赋值为负无穷大防止一些非法状态对结果的影响。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
ll dp[maxn][205];
struct P
{
int a, p[7];
bool operator<(const P &C) const
{
return a > C.a;
}
} s[maxn];
int main()
{
int n, p, k;
scanf("%d%d%d", &n, &p, &k);
for (int i = 1; i <= n; i++)
scanf("%d", &s[i].a);
for (int i = 1; i <= n; i++)
for (int j = 0; j < p; j++)
scanf("%d", &s[i].p[j]);
sort(s + 1, s + n + 1);
memset(dp, -INF, sizeof(dp));
dp[0][0] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < (1 << p); j++)
{
if (i - __builtin_popcount(j) <= k && i <= k + p)
dp[i][j] = max(dp[i][j], dp[i - 1][j] + s[i].a);
else
dp[i][j] = dp[i - 1][j];
for (int t = 0; t < p; t++)
if (j & (1 << t))
dp[i][j] = max(dp[i][j], dp[i - 1][j - (1 << t)] + s[i].p[t]);
}
}
printf("%lld\n", dp[n][(1 << p) - 1]);
return 0;
}
京公网安备 11010502036488号