欢乐qwq 欢乐是什么
B. 凑数
本来以为就连a，b的单价都比1高的时候也可以贪心，直接能操作就操作到不能操作为止 原来还需要枚举！？…… 可以计算出三种选择的单价，如果1最优那就可以直接凑了，如果1次优也可以直接凑，但是如果1最劣的话就不能按照把单价最高的先选完之类的顺序贪心，不能贪心那就枚举。 假设B的单价最低，它肯定不能被选超过n / B次，C的最大次数是B-1，因为C选了B次之后凑成的数就包含了B的倍数，可以直接换成B。code
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int maxn = 2e5 + 3;
const int inf = 0x7fffffff;
int T, n;
ll A, B, X, Y, Z;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
signed main()
{
freopen("cs.in", "r", stdin);
freopen("cs.out", "w", stdout);
T = read();
while(T--)
{
n = read(); A = read(); B = read(); X = read(); Y = read(); Z = read();
if(Y * B > A * Z)
{
swap(A, B); swap(Y, Z);
}
if(X * A <= Y)
{
printf("%llu\n", n * X);
}
else if(X * B <= Z)
{
printf("%llu\n", n / A * Y + n % A * X);
}
else
{
ll ans = (1llu<<63) - 1;
if(n / A < A - 1)
{
for(int i=0; i<=n/A; i++)
{
ll s = n - i * A;
ans = min(ans, i * Y + s / B * Z + s % B * X);
}
}
else
{
for(int i=0; i<=A-1; i++)
{
ll s = n - i * B;
ans = min(ans, i * Z + s / A * Y + s % A * X);
}
}
printf("%llu\n", ans);
}
}
return 0;
}
C. 同构
这都能打表！？没想过…… 我只想到了两个数的质因数种类完全一样，还有1可以和任意大于n/2的质数交换，然后总觉得还有其他情况可以交换却不知道其他情况是什么 而且管局质因数种类完全一样应该怎么判断，第一印象是bitset，复杂度怎么想都不对 其实用乘积就可以判断了，不用考虑重复，一个质数肯定不能被其他质数用乘积表示出来，然而取模？？ 为什么居然可以取模？？？难道取模后这个范围一定会落在n以下吗？？ 先鹤为快 啊我傻了。。关于把小于n的某数分解质因数，还不带指数的把它们乘起来，能大于n也就怪了 所以不用取模本来就在n以下，那我就不mod了 所以互换的条件是： 1.两个数因数的种类完全一样 2.若对于质数p1，p2，(向下取整)n / p1 == n / p2时，即1到n中所有p1的倍数和p2的倍数可以一一对应，那么对应互换，这两个交换相互独立。code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 3;
const int mod = 1e9 + 7;
int n, ans=1, p[maxn], jc[maxn], mn[maxn], cnt1[maxn], cnt2[maxn], tmp[maxn], num[maxn];
bool v[maxn];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
void primes(int n)
{
jc[0] = jc[1] = 1;
for(int i=2; i<=n; i++)
{
jc[i] = 1ll * jc[i-1] * i % mod;
if(!v[i]) p[++p[0]] = i, mn[i] = i;
for(int j=1; j<=p[0]&&i*p[j]<=n; j++)
{
v[i*p[j]] = true; mn[i*p[j]] = p[j];
if(i % p[j] == 0) break;
}
}
}
int main()
{
freopen("tg.in", "r", stdin);
freopen("tg.out", "w", stdout);
n = read(); primes(n);
num[1] = 1; cnt2[1]++;
for(int i=2; i<=n; i++)
{
int ret = i; tmp[i] = 1;
while(ret > 1)
{
int prm = mn[ret];
while(ret % prm == 0) ret /= prm;
tmp[i] = 1ll * tmp[i] * prm;//mod什么鬼
}
cnt1[tmp[i]]++;
}
for(int i=1; i<=p[0]; i++)
{
num[p[i]] = n / p[i];
cnt2[num[p[i]]]++;
}
for(int i=1; i<=n; i++) ans = 1ll * ans * jc[cnt1[i]] % mod * jc[cnt2[i]] % mod;
printf("%d\n", ans);
return 0;
}
D. 重建
%%%Delov
有一道类似的删边题可以给我们灵感：Picnic Planning，思路相似但是具体做法好像还是很有差别，我差点以为只有邻接矩阵才支持删边。
这两个删边的题的区别是什么？一个是边连接边删除而另一个是在已经构成最小生成树的基础上删除？另一个没有能删的边和不能删的边之分，特殊点可以看做和Park直接相连的点？所以不就也可以看成树已经建好了？？不把同一个城市不同火车站连出去的高铁拆开，权值相等一起计算贡献？这两道题算法不能共用的理由只是数据范围？？总感觉就是一样的。。。 但是由于Picnic Planning我还没有A，只会蓝书上的理论，还是先A再对比吧。。 如果r = 1，只需要把每个城市内部建出来最小生成树，把前l-1小的加上就行了(高铁是使两个城市连通的唯一渠道)，但是如果r更大，那就有了一些点只在一个城市里连通，剩下的城市只要接上对应点，就可以删掉多余的边。 边不会删重因为已经合并了，每次拿出来的是等效的小b，最终必须要剩下的那个内部拥有完全连通的生成树的图一定是b最小的那个。code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 3;
int n, m, l, r, a[maxn], b[maxn], fa[maxn], mark[maxn], stk[maxn];
int top, rk[maxn];
ll ans,sum, suf[maxn];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
struct edge
{
int u, v, w;
bool operator < (const edge &T) const
{
return w < T.w;
}
}e[maxn];
int find(int x)
{
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
bool cmp(int x, int y)
{
return a[x] < a[y];
}
int main()
{
freopen("rb.in", "r", stdin);
freopen("rb.out", "w", stdout);
n = read(); m = read();
for(int i=1; i<=m; i++)
{
e[i].u = read()+1, e[i].v = read()+1;
e[i].w = read();
}
l = read();
for(int i=0; i<l; i++)
{
a[i] = read(); b[i] = read();
}
r = read();
for(int i=1,s; i<=r; i++)
{
s = read()+1; mark[s] = 1;
}
for(int i=1; i<=n; i++) fa[i] = i;
//按照边权从小到大合并，预处理之后m = n - 1且所有火车站都是枢纽车站
sort(e+1, e+1+m);
for(int i=1; i<=m; i++)
{
int u = find(e[i].u), v = find(e[i].v);
if(u == v) continue;
sum += e[i].w;
if(mark[u] && mark[v]) stk[++top] = e[i].w;//只有这样的边才有可能被替代
//否则断开之后形成的连通块中，至少有一个不能与其他城市连通
fa[u] = v;
mark[v] |= mark[u];
}
//stk自动有序
for(int i=top; i; i--)
{
suf[i] = suf[i+1] + stk[i];
}
ans = sum * l;
for(int i=0; i<l; i++)
{
ans += 1ll * b[i] * (n - 1);
}
//先假设每条边都连起来了，再考虑把不需要的边断开
for(int i=0; i<l; i++)
{
rk[i] = i, fa[i] = i;
}
//按a从小到大考虑每个城市
//假设arg min ai = 1，且b1 < b2
//城市1连得边是城市2连的边的超集，因此城市2目前的每个连通块都会向城市1连恰好一条高铁线路
//高铁没有要求必须建，但是前l-1条高铁一定要建，建的话就可以删掉能删的边
sort(rk, rk+l, cmp);
for(int i=0; i<l-1; i++)
{
int u = find(rk[i]), v = find((rk[i]+1)%l);
if(b[u] < b[v]) swap(u, v);
fa[u] = v;
int p = lower_bound(stk+1, stk+1+top, a[rk[i]]-b[u])-stk;
ans -= suf[p] + 1ll * (top - p + 1) * b[u];
ans += 1ll * (top - p + 2) * a[rk[i]];
}
printf("%lld\n", ans);
return 0;
}