https://codeforces.com/gym/104077
C. Clone Ranran
签到题
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
LL a, b, c;
LL divup(LL a, LL b){
if(a % b == 0)
return a / b;
return a / b + 1;
}
void sol(){
scanf("%lld%lld%lld", &a, &b, &c);
int k = 0, s = 1;
LL ans = c * b, tmp;
do{
k++;
s <<= 1;
tmp = k * a + divup(c, s) * b;
ans = min(ans, tmp);
// printf("k=%2d s=%3lld tmp=%lld\n", k, s, tmp);
}while(s <= c);
printf("%lld\n", ans);
// printf("\n");
}
int main(){
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
int T;
scanf("%d", &T);
while(T--)
sol();
return 0;
}
F. Hotel
签到题
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
void solve();
int main(){
int T;T=1;
while(T--)solve();
return 0;
}
void solve(){
int n;
ll c1,c2,ans=0;
string s;
cin>>n>>c1>>c2;
for(int i=1;i<=n;i++){
cin>>s;
int sum=0;
if(s[0]==s[1]||s[0]==s[2]||s[1]==s[2])sum++;
if(sum)
ans+=c2+min(c2,c1);
else ans+=min(c1,c2)*3;
}if(c1*2<=c2){
cout<<n*3*c1;
return;
}
cout<<ans;
}
G. Perfect Word
分析：
很好想到对字符串按长度排序 (开始写错了就是因为按照字典序排序了)
依次考虑排序后的字符串
假如当前串为s[0,j]
如果s[0,j-1] 和 s[1,j] trie树中都出现过 那么我们将s[0,j]也加入trie树中
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=1e5+5;
int tr[maxn][27],tot,cnt,ans=0;
string s[maxn],t;
void ins(string ch) {
int rt = 0;
int len=ch.size();
for (int i = 0; i < len; i++) {
if (!tr[rt][ch[i] - 'a'])
tr[rt][ch[i] - 'a'] = ++tot;
rt = tr[rt][ch[i] - 'a'];
}
}
bool find(string s)
{
int rt=0;
int len=s.size();
for(int i=0;i<len;i++)
{
if(!tr[rt][s[i]-'a']) return false;
rt=tr[rt][s[i]-'a'];
}
return true;
}
bool cmp(string aa,string bb){
if(aa.size()!=bb.size())return aa.size()<bb.size();
return aa<bb;
}
void solve();
int main(){
int T;T=1;
while(T--)solve();
return 0;
}
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>t;
if(t.size()==1)ins(t),ans=1;
else s[++cnt]=t;
}
sort(s+1,s+1+cnt,cmp);
for(int i=1;i<=cnt;i++){
int j=s[i].size();
if(find(s[i].substr(1,j))&&find(s[i].substr(0,j-1)))
ans=max(ans,j),ins(s[i]);
}
cout<<ans;
}
L. tree
分析
不知道是我们太菜了还是太卷了 这道题我们是费尽脑汁才做出来的
开始想的是树形dp 发现方程都设不出来
换个想法 那就硬搞 首先想到把最长链给找出来 然后依次找除去最大链的次大
这个可以用长链剖分
对于这些长度降序的链 一定保证相同长度的链与链之间的点不存在祖先关系
如果不是先找最大再找次大而是随意遍历的话就可能存在祖先关系
假如总共有cnt条链 然后遍历一遍 前i个用满足第一个条件 需要用i个 后面所有的满足第二个条件 需要用 len[i+1]个
对于每种情况取个min即可
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int N=1e6+5;
int n;
void solve();
void dfs(int,int);
bool cmp(int aa,int bb){
return aa>bb;
}
vector<int>Q[N];
int ans[N];
int cnt;
int main(){
int T;cin>>T;
while(T--)solve();
return 0;
}
int len[N], hson[N], top[N];
void dfs1(int p) {
len[p] = 1;
for (int i=0;i<Q[p].size();i++){
int q=Q[p][i];
dfs1(q);
if (len[q] + 1 > len[p])
hson[p] = q, len[p] = len[q] + 1;
}
}
void dfs2(int p, int tp) {
top[p] = tp;
if (hson[p]) dfs2(hson[p], tp);
for (int i=0;i<Q[p].size();i++){
int q=Q[p][i];
if (!top[q])
dfs2(q, q);
}
}
void cut() {
dfs1(1);
dfs2(1, 1);
}
void solve(){
scanf("%d",&n);cnt=0;
for(int i=1;i<=n;i++)Q[i].clear(),len[i]=hson[i]=top[i]=0;
for(int i=2,x;i<=n;i++)scanf("%d",&x),Q[x].push_back(i);
cut();
for(int i=1;i<=n;i++)
if(top[i]==i)ans[++cnt]=len[i];
sort(ans+1,ans+1+cnt,cmp);
int res=1e9+7;
ans[cnt+1]=0;
for(int i=0;i<=cnt;i++)
res=min(res,i+ans[i+1]);
cout<<res<<endl;
}
E. Find Maximum(待补)
分析
思路可能出现了问题 调了很久都没调出来
B. Cells Coloring(待补)
分析：
网络流
标签：2022,int,void,len,ICPC,long,西安,ans,include From： https://www.cnblogs.com/wzxbeliever/p/16939268.html