埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛-移动直播平台-世界杯足球比赛|世界杯音乐|iPhone圣地世界杯移动观赛站|iphonesd.com

2025-08-21 22:09:31
admin

比赛链接

组队打翻车了（哭）

A:Wasserstein Distance

因为注意到对于要搬运的土K，把它从A搬运到C，和把它从A搬运到B再搬运到C所付出的代价是一样的（其中A

根据这一点我们可以算出当前列中目标土堆和现有土堆的差距，这个差距的绝对值表示要使当前土堆变成目标土堆一定要付出的代价，并把这个差距留给下一列从而达到达到之前所说的传递效果。（说实话还是看代码好一点，笔者语文已经被队友吐槽过了）

#include

using namespace std;

const int maxn = (int)(1e5)+1000;

const int inf = 0x3f3f3f3f;

const int mod = 998244353;

const double eps = 1e-6;

typedef long long LL;

typedef unsigned long long ull;

LL num[maxn], tar[maxn];

LL Labs(LL a) {

if (a > 0) return a;

return -a;

}

int main() {

//freopen("E:\\test.txt", "r", stdin);

int t;

scanf("%d", &t);

while (t--) {

int n;

scanf("%d", &n);

for (int i = 0; i < n; i++)

scanf("%lld", &num[i]);

for (int i = 0; i < n; i++)

scanf("%lld", &tar[i]);

LL left = 0, ans = 0;

for (int i = 0; i < n; i++) {

num[i] += left;

left = num[i] - tar[i];

ans += Labs(left);

}

printf("%lld\n", ans);

}

return 0;

}

B:合约数

因为节点的权值val只有1e4,我们可以先打出这些数字他们的合约数有哪些，达到快速查询（打表方法根据素数筛）。

首先暴力是明显过不了的，考虑到对于某一颗子树，如果先用一个数组记录它根节点对答案的所有可能的贡献（下表为该节点权值的合约数时，加上节点的编号），当访问这个子树的某个节点恰好为根节点的合约数的时候可以直接加上之前处理过的贡献。之后只要在访问完这个节点的时候把这个贡献删掉就行了，整体时间复杂度下降为O(树的节点数）。

#include

using namespace std;

const int maxn = (int)(1e4) + 100;

const int inf = 0x3f3f3f3f;

const int mod = (int)1e9 + 7;

const double eps = 1e-6;

typedef long long LL;

typedef unsigned long long ull;

bool nisp[maxn];

vector hc[maxn], edge[maxn * 4];

int val[maxn * 2];

LL ans, cnt[maxn * 2];

void init() {

memset(nisp, 0, sizeof(nisp));

for (int i = 2; i < maxn; i++)//素数筛

if (!nisp[i])

for (int j = i * 2; j < maxn; j += i)

nisp[j] = 1;

for (int i = 2; i < maxn; i++) {

if (!nisp[i]) continue;

for (int j = i; j < maxn; j+=i)

hc[j].push_back(i);

}

void dfs(int u, int pre) {

for (int i = 0; i < hc[val[u]].size(); i++)//处理出该节点可能的贡献

cnt[hc[val[u]][i]] = (cnt[hc[val[u]][i]] + mod + u) % mod;

ans = (ans + cnt[val[u]]) % mod;

for (int i = 0; i < edge[u].size(); i++) {

int v = edge[u][i];

if (v == pre) continue;

dfs(v, u);

}

for (int i = 0; i < hc[val[u]].size(); i++)//删除该节点可能的贡献

cnt[hc[val[u]][i]] = (cnt[hc[val[u]][i]] + mod - u) % mod;

}

int main() {

init();

int t;

scanf("%d", &t);

while (t--) {

int n, root;

scanf("%d%d", &n, &root);

for (int i = 1; i <= n; i++)

edge[i].clear();

int u, v;

for (int i = 0; i < n - 1; i++) {

scanf("%d%d", &u, &v);

edge[u].push_back(v);

edge[v].push_back(u);

}

for (int i = 1; i <= n; i++)

scanf("%d", &val[i]);

ans = 0;

dfs(root, -1);

printf("%lld\n", ans);

}

return 0;

}

C:序列变换

观察可知魔法2和魔法3性质一致，所以只要一开始确定两个数的大小（例如笔者是只用魔法3的，遇到两个数的时候总是使它们升序）就可以省略一种魔法。然后观察数据量只有9，那么魔法1（交换魔法）就可以通过全排列函数打出所有交换结果，全排列需要时间为N!。然后N^2预处理出a序列中的数到b序列中每个数用魔法3所需要付出的代价，通过这个表确定排列序列用魔法2付出的代价，最后加上原序列到达排列序列所需要的最小交换次数就行了（这里计算交换次数笔者用了选择排序原理，实际上应该有更快的，暂时想不出来），实际时间复杂度为 O(N!*N^2+N^2*LOG(MAX(A)) 其中a为两个序列中的最大数。

#include

using namespace std;

const int maxn = (int)(1e4) + 100;

const int inf = 0x3f3f3f3f;

const int mod = (int)1e9 + 7;

const double eps = 1e-6;

typedef long long LL;

typedef unsigned long long ull;

int np[15], tnp[15];

int cost[15][15];

int numa[15], numb[15];

int n;

int fun1(int i, int j) {//计算魔法3的代价

int x = numa[i], y = numb[j];

if (x == y) return 0;

else if (x > y) swap(x, y);

int cnt = 0;

while (y / 2 >= x) {

cnt += y % 2 + 1;

y /= 2;

}

cnt += y - x;

return cnt;

}

int fun2() {//计算交换的代价

for (int i = 0; i < n; i++)

tnp[i] = np[i];

int cnt = 0;

for (int i = 0; i < n; i++) {

if (i == np[i]) continue;

else {

for (int j = i + 1; j < n; j++)

if (tnp[j] == i) {

swap(tnp[i], tnp[j]);

cnt++;

break;

}

return cnt;

}

int solve() {

int ans = fun2();

for (int i = 0; i < n; i++)

ans += cost[i][np[i]];

return ans;

}

int main() {

int t;

scanf("%d", &t);

while (t--) {

scanf("%d", &n);

for (int i = 0; i < n; i++)

scanf("%d", &numa[i]);

for (int i = 0; i < n; i++) {

scanf("%d", &numb[i]);

np[i] = i;

}

for (int i = 0; i < n; i++)

for (int j = 0; j < n; j++)

cost[i][j] = fun1(i, j);//预处理魔法3的代价表

int ans = inf;

do {

ans = min(ans, solve());

} while (next_permutation(np, np + n));//全排列函数

printf("%d\n", ans);

}

return 0;

}

D:数字游戏

暂时保留

网上有些找规律的代码是有bug的.

结论如果R2-L2>=MOD-1就 LOSE，反之则WIN。

然而这个结论是错误

例如7 7 1 3 6，明显是LOSE。

不过对于R2-L2>=MOD-1，这是必败态。

（数据不够强啊，怪不得这么多少人过了）

E:小Y吃苹果

n=1时，1可以由2,3得来.

n=2时，对于2可以由4,5得来 3可以由6,7得来

.........

显然就是2^n

#include

using namespace std;

const int maxn = 2*(int)(1e5)+1000;

const int inf = 0x3f3f3f3f;

const int mod = 998244353;

const double eps = 1e-6;

typedef long long LL;

typedef unsigned long long ull;

int a[25];

void init() {

a[0] = 1;

for (int i = 1; i <= 22; i++)

a[i] = a[i - 1] * 2;

}

int main() {

//freopen("E:\\test.txt", "r", stdin);

init();

int n;

while (~scanf("%d", &n)) {

printf("%d\n", a[n]);

}

return 0;

}

F:1 + 2 = 3?

当只有一位时，就只有1两位时，至于10三位时，100、101四位时，1000、1001、1010

用数组dp保持第i位时的数量，很容易发现dp[i] = dp[i-1] + dp[i-2];

显然为一个斐波那契数列，前n项和表的下表代表对应位是否有1.

可以先预处理出斐波那契表的前n项和，通过不断查找这个数在前n项和表的第几位从而确定第几位是1，然后用这个数-取前n项和表不断递归直到为0.

#include

using namespace std;

const int maxn = (int)(1e5)+1000;

const int inf = 0x3f3f3f3f;

const int mod = 998244353;

const double eps = 1e-6;

typedef long long LL;

typedef unsigned long long ull;

LL fab[100], sum[110];

int vis[maxn];

int Max;

void init() {

fab[1] = fab[2] = 1;

for (int i = 3; i <= 92; i++)

fab[i] = fab[i - 1] + fab[i - 2];

sum[1] = 1;

for (int i = 2; i <= 60; i++)

sum[i] = sum[i - 1] + fab[i];

}

void work(LL n) {

if (n == 0)

return;

int pos = lower_bound(sum, sum + 61, n) - sum;

Max = max(Max, pos);

vis[pos] = 1;

work(n - sum[pos-1]-1);

return;

}

int main() {

init();

LL n;

LL t;

while (~scanf("%lld", &t)) {

for (int z = 1; z <= t; z++) {

scanf("%lld", &n);

memset(vis, 0, sizeof(vis));

Max = 0;

work(n);

long long ans = 0;

for (int i = Max; i >= 1; i--) {

ans *= 2;

if (vis[i] == 1) {

ans += 1;

//printf("1");

}

//else

//printf("0");

}

//printf(" %d %lld\n",Max,ans);

printf("%lld\n",ans);

}

//freopen("E:\\test.txt", "r", stdin);

return 0;

}

G:小Y做比赛

待补

H:小Y与多米诺骨牌

待补

I:二数

找到第一个奇数后使它变成偶数的最小代价明显是+1或者-1，如果是+1的话明显后面全部变为0的代价最小，如果是-1的话后面全变成8的代价最小。问题转化为(x-1)00000...和（x+1)88888.....哪个代价最小

比赛时笔者傻傻的写了一个高精度减法。

其实这个还是有规律的，通过比较得知当x后面接的是都是4的话两种变化代价是一样的，那么只要找出后面第一个不是4的数，和4比较大小，如果>4就+的操作，如果<4就用-的操作。如果没有的话就用-的操作（题目要求输出小的那个）

#include

using namespace std;

const int maxn = (int)(1e5) + 10;

const int inf = 0x3f3f3f3f;

const int mod = 998244353;

const double eps = 1e-6;

typedef long long LL;

typedef unsigned long long ull;

char str[maxn];

int len;

void change(int pos, int type) {

if (type == 1) {

str[pos]--;

for (int i = pos + 1; i < len; i++)

str[i] = '8';

}

else {

str[pos]++;

for (int i = pos + 1; i < len; i++)

str[i] = '0';

}

int main() {

int t;

scanf("%d", &t);

while (t--) {

scanf("%s", str);

len = strlen(str);

int pos = -1;

for (int i = 0; i < len; i++) {

if ((str[i] - '0') & 1) {

pos = i;

break;

}

if (pos == -1) printf("%s\n", str);

else {

if (str[pos] == '9')

change(pos, 1);

else {

int flag = 1;

for (int i = pos + 1; i < len; i++) {

if (str[i] > '4') {

flag = 2;

break;

}

else if (str[i] < '4')

break;

}

change(pos, flag);

}

bool f = false;

for (int i = 0; i < len - 1; i++) {

if (str[i] != '0')

f = true;

if (f)

printf("%c", str[i]);

}

printf("%c\n", str[len - 1]);

}

return 0;

}

J:小Y写文章

待补

K:树上最大值

待补

L:K序列

因为序列和为k的倍数，所以对其%k为0，这样问题可以转化为背包问题，重量为数字本身，价值都为1，并且重量求和时要%k

因为题目给出nk<1e7所以不能二位数组，但是可以用滚动数组解决（疯狂暗示背包然而我想到了前缀和的算法）

#include

using namespace std;

const int maxn = (int)(1e7) + 10;

const int inf = 0x3f3f3f3f;

const int mod = 998244353;

const double eps = 1e-6;

typedef long long LL;

typedef unsigned long long ull;

int dp[2][maxn], a[maxn];

int main(){

int n, k;

while (~scanf("%d%d", &n, &k)) {

for (int i = 1; i <= n; i++)

scanf("%d", &a[i]);

for (int i = 0; i <= k; i++)

dp[0][i] = -inf;

int p = 0;

dp[0][0] = 0;

for (int i = 1; i <= n; i++){

p ^= 1;

for (int j = 0; j < k; j++)

dp[p][(j + a[i]) % k] = max(dp[p ^ 1][(j + a[i]) % k], dp[p ^ 1][j] + 1);

}

printf("%d\n", dp[p][0]);

}

return 0;

}

埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛

国产杜兰特！2米06北京前锋两战24中19