倒序开吧, 你们最想看的应该是D题的题解, 我干了两个小时才搞懂
题意分析: 给定 n n n 种原料, n ? 1 n - 1 n?1 个约束条件, 每种原料的比值必须要满足约束关系, 然后求原料含量最小的总和
首先不妨将题意转化一下,
n
,
n
?
1
n, n - 1
n,n?1, 不难想到是树, 知道是树后, 可以将
n
n
n 种原料看作
n
n
n 个点,
n
?
1
n - 1
n?1 个约束条件可以看作
n
?
1
n - 1
n?1 条边, 然后每两个点之间,要满足点权比等于边权, 我们不妨可以画一个图
a
i
:
a
j
=
x
/
y
a_i : a_j = x / y
ai?:aj?=x/y
a
j
=
a
i
?
y
/
x
a_j = a_i * y / x
aj?=ai??y/x
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353, N = 2e5 + 10;
int qmi(int a,int b) //快速幂模板
{
int res = 1;
while(b)
{
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int n,t;
int Inv[200005];
struct node
{
int v, x, y;
};
vector<node>e[N];
int cnt[200005],Maxcnt[200005];
void Add(int x,int flag) //处理乘除法 当乘x时, 就 减去, 除x时就加上
{
for(int i=2;i * i <= x; i ++) //质因数
{
while(x % i == 0)
{
cnt[i] += flag;
x/=i;
Maxcnt[i] = max(Maxcnt[i], cnt[i]); //更新质因子i的最大数量
}
}
if(x != 1) //剩下未处理的
{
cnt[x] += flag;
Maxcnt[x] = max(Maxcnt[x], cnt[x]);
}
}
void dfs1(int u,int fa,int x = 1,int y = 1)
{
Add(y,-1); //处理乘y
Add(x,1); //处理除x
for(auto &p : e[u]) //遍历树上的每条边
{
if(p.v == fa) continue; //走到头了
dfs1(p.v, u, p.x,p.y); //往下搜
}
Add(x, -1); //回溯
Add(y, 1); //回溯
}
int Nowval,ans;
void dfs2(int u,int fa,int x = 1,int y = 1)
{
Nowval = Nowval * y % mod * Inv[x] % mod; //乘上 x/y
ans = (ans + Nowval) % mod; //加上该点的点权
for(auto &p : e[u]) //递归
{
if(p.v == fa) continue;
dfs2(p.v,u,p.x,p.y);
}
Nowval = Nowval * x % mod * Inv[y] % mod; //回溯
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0), cout.tie(0);
cin >> t;
while(t--)
{
cin >> n;
for(int i = 1; i <= n; i ++) Inv[i] = qmi(i, mod-2);//乘法逆元
for(int i = 1; i <= n; i ++) e[i].clear();
for(int i = 1; i <= n; i ++) cnt[i] = Maxcnt[i] = 0; //初始化
for(int i = 1;i <= n - 1; i ++)
{
int u,v,x,y;
cin >> u >> v >> x >> y;
e[u].push_back({v, x, y});
e[v].push_back({u, y, x});
}
dfs1(1, 0); //跑一遍计算maxcnt
Nowval = 1;
ans = 0;
for(int i = 1; i <= n; i ++)
Nowval = (Nowval * qmi(i, Maxcnt[i])) % mod; //计算出节点1的点权
dfs2(1, 0);
cout << ans << '\n';
}
}
题意: 有一块重量为 w w w 的蛋糕, 可以切 n ? 1 n - 1 n?1 次, 每次切出来的蛋糕重量为 w / 2 w / 2 w/2 向下取整,和 w / 2 w / 2 w/2 向上取整, 给定了一个 一个蛋糕被切了 n ? 1 n - 1 n?1 次后的每一块蛋糕的重量, 判断这种序列是否存在
首先我们可以模拟切的过程, 先计算出蛋糕的总质量, 然后模拟切的过程, 维护两个优先队列, 一个负责模拟切的过程, 一个是保存给定序列的蛋糕的重量, 每切一次后, 将最大重量的相同的蛋糕去掉, 然后切完后判断另一个队列是否为空即可
#include<bits/stdc++.h>
#define int long long
using namespace std;
void solve()
{
priority_queue<int,vector<int>,less<int>>heap, s;
//s1 是负责模拟切的过程 s2 是维护给定的序列
int n, x;
cin >> n;
int sum = 0;
for(int i = 1; i <= n; i ++ ) cin >> x,sum += x, s.push(x);
heap.push(sum); //入队
while(1)
{
if(heap.top() < s.top()) //不合题意, 一定不存在
{
cout << "NO\n";
return;
}
while(heap.top() == s.top()) //去除最大的,重量相同的蛋糕
{
heap.pop();
s.pop();
if(heap.empty()) break; //切完了,退出
}
if(heap.empty()) break; //切完了,退出
int a = heap.top(); //去除堆顶
heap.pop();
heap.push(a / 2), heap.push((a + 1 ) / 2); //切蛋糕
if(a / 2 == 0) break; //切完了,退出循环
}
if(heap.empty()) cout << "YES\n";
else cout << "NO\n";
}
signed main()
{
int t;
cin >> t;
while(t -- ) solve();
}
题意分析: 大概就是说把后面出现过的字符给它删去吧,大概就这个意思
#include<bits/stdc++.h>
#define int long long
using namespace std;
int cnt[110];
signed main()
{
int t;
cin >> t;
while(t -- )
{
string s;
memset(cnt, 0, sizeof cnt); //初始化数组
cin >> s;
for(int i = 0; i < (int)s.size(); i ++ )
cnt[s[i] - '0']++; //记录每个字符出现的次数
int bg = 0; //记录起始位置
for(int i = 0; i < (int)s.size(); i ++ ) //如果该字符在后面出现过, 就往后移
if(cnt[s[i] - '0'] > 1) bg = i + 1,cnt[s[i] - '0']--; //删去这个字符
else break; // 当遇到一个只出现过一次的字符,退出
if(bg == (int)s.size()) bg --; //因为前面记录的能够删去的字符的后面一个位置,所以要从它前面那个开始
for(int i = bg; i < (int)s.size(); i ++ ) //打印
cout << s[i];
cout << '\n';
}
}
题意分析: 就是要求蛋糕的味道的最大值, 其值就是两个相邻蛋糕间的和的最大值, 然后因为可以改变顺序, 所以一定有一种方法可以让最大和次大值相邻, 所以直接输出最大值和次大值之和即可
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[1100];
signed main()
{
int t;
cin >> t;
while(t -- )
{
int n;
cin >> n;
for(int i = 1; i <= n; i ++ )
cin >> a[i];
sort(a + 1, a + 1 + n);
cout << a[n] + a[n - 1] << '\n';
}
}