C.Clone Ranran
题意:一个人要准备一场比赛,需要出c道题,他现在可以选择两种操作:1.花费a分钟自我复制一次。(复制的自己也可以接着复制)2.花费b分钟出一道题。问最短要多少分钟可以准备c道题。
思路:枚举自我复制的次数,挨个判断就行。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> using namespace std; #define ll long long #define rg register #define maxn 425450 #define P 131 #define int long long #define INF 0X7F7F7F #pragma GCC optimize(3) #pragma -fcrossjumping #pragma -fdefer-pop #pragma -fmerge-constans #pragma -fthread-jumps #pragma -floop-optimize #pragma -fif-conversion #pragma -fif-conversion2 #pragma -fdelayed-branch #pragma -fguess-branch-probability #pragma -fcprop-registers #pragma -fforce-mem #pragma -foptimize-sibling-calls #pragma -fstrength-reduce #pragma -fgcse #pragma -fcse-follow-jumps #pragma -frerun-cse-after-loop #pragma -fdelete-null-pointer-checks #pragma -fextensive-optimizations #pragma -fregmove #pragma -fschedule-insns #pragma -fsched-interblock #pragma -fcaller-saves #pragma -fpeephole2 #pragma -freorder-blocks #pragma -fstrict-aliasing #pragma -funit-at-a-time #pragma -falign-functions #pragma -fcrossjumping #pragma -finline-functions #pragma -fweb inline int read() { int x=0,f=1; char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c<='9'&&c>='0') { x=(x<<1)+(x<<3)+(c^48); c=getchar(); } return x*f; } inline void write(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) write(x/10); putchar(x%10+'0'); } inline mul(int a,int b) { int sum=1; while(b) { if(b&1) sum=sum*a; a=a*a; b>>=1; } return sum; } int t,a,b,c; signed main() { t=read(); while(t--) { a=read(),b=read(),c=read(); int ans=1e9+5; for(rg int i=0;;++i) { int num=mul(2,i); ans=min(ans,a*i+(int)ceil((double)c*1.0/(double)num*1.0)*b); if(num>=c) { cout<<min(ans,i*a+b)<<endl; break; } } } }View Code
E. Find Maximum
题意:给你一个函数 f(x),同时给t组询问,每次询问给出一个范围[l,r],求这个范围中最大的 f(x)。
思路:将整数变成三进制形式观察,我们可以发现对于任意一个三进制形式的数,它的f(x)的值等于它各个位置上的数之和+它本身的长度。因此靠着这个性质可以采用贪心的思路来做。要想f(x)尽可能大,第一是需要数本身够长,第二就是需要各个位置上的2尽可能得多,因此可以枚举2的数量来进行判断。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> using namespace std; #define ll long long #define rg register #define maxn 125450 #define P 131 #define int long long //#define int __int128 #define INF 0X7F7F7F #pragma GCC optimize(3) #pragma -fcrossjumping #pragma -fdefer-pop #pragma -fmerge-constans #pragma -fthread-jumps #pragma -floop-optimize #pragma -fif-conversion #pragma -fif-conversion2 #pragma -fdelayed-branch #pragma -fguess-branch-probability #pragma -fcprop-registers #pragma -fforce-mem #pragma -foptimize-sibling-calls #pragma -fstrength-reduce #pragma -fgcse #pragma -fcse-follow-jumps #pragma -frerun-cse-after-loop #pragma -fdelete-null-pointer-checks #pragma -fextensive-optimizations #pragma -fregmove #pragma -fschedule-insns #pragma -fsched-interblock #pragma -fcaller-saves #pragma -fpeephole2 #pragma -freorder-blocks #pragma -fstrict-aliasing #pragma -funit-at-a-time #pragma -falign-functions #pragma -fcrossjumping #pragma -finline-functions #pragma -fweb inline int read() { int x=0,f=1; char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c<='9'&&c>='0') { x=(x<<1)+(x<<3)+(c^48); c=getchar(); } return x*f; } inline void write(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) write(x/10); putchar(x%10+'0'); } inline mul(int a,int b) { int sum=1; while(b) { if(b&1) sum=sum*a; a=a*a; b>>=1; } return sum; } inline int f(int x) { if(x==0) return 1; else if(x%3==0) return f(x/3)+1; else return f(x-1)+1; } inline int get(int temp,int num) { int tot=0; while(num!=0) { tot=0; while(temp%3!=0) { ++tot; temp--; } temp/=3; --num; } tot=0; while(temp%3!=0) { ++tot; temp--; } return tot; } int t,l,r; inline void work(int temp) { int ans=max(f(l),f(r)); vector<int>v; while(temp) { v.push_back(temp%3); temp/=3; } reverse(v.begin(),v.end()); for(rg int i=0;i<v.size();++i) { if(v[i]==0) continue; temp=0; for(rg int j=0;j<=i;++j) temp=temp*3+v[j]; temp--; for(rg int j=i+1;j<v.size();++j) temp=temp*3+2; if(temp>=l&&temp<=r) ans=max(ans,f(temp)); } cout<<ans<<endl; } signed main() { t=read(); while(t--) { l=read(),r=read(); work(r); } }View Code
F. Hotel
题意:签到题,需要考虑的点主要是有可能单人房比双人间还贵,所以三个人可以开三个双人间这种。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> using namespace std; #define ll long long #define rg register #define maxn 545 #define P 131 #define int long long #define INF 0X7F7F7F #pragma GCC optimize(3) #pragma -fcrossjumping #pragma -fdefer-pop #pragma -fmerge-constans #pragma -fthread-jumps #pragma -floop-optimize #pragma -fif-conversion #pragma -fif-conversion2 #pragma -fdelayed-branch #pragma -fguess-branch-probability #pragma -fcprop-registers #pragma -fforce-mem #pragma -foptimize-sibling-calls #pragma -fstrength-reduce #pragma -fgcse #pragma -fcse-follow-jumps #pragma -frerun-cse-after-loop #pragma -fdelete-null-pointer-checks #pragma -fextensive-optimizations #pragma -fregmove #pragma -fschedule-insns #pragma -fsched-interblock #pragma -fcaller-saves #pragma -fpeephole2 #pragma -freorder-blocks #pragma -fstrict-aliasing #pragma -funit-at-a-time #pragma -falign-functions #pragma -fcrossjumping #pragma -finline-functions #pragma -fweb inline int read() { int x=0,f=1; char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c<='9'&&c>='0') { x=(x<<1)+(x<<3)+(c^48); c=getchar(); } return x*f; } inline void write(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) write(x/10); putchar(x%10+'0'); } int n; int cost1,cost2,ans;//单人 双人 signed main() { n=read(); cost1=read(),cost2=read(); for(rg int i=1;i<=n;++i) { string s; cin>>s; int num1=1,num2=0,num3=0; if(s[1]==s[0]) num1++; else num2++; if(s[2]==s[0]) num1++; else if(s[2]==s[1]) num2++; else num3++; if(num1==1) ans+=min(cost1,cost2); else if(num1==2) ans+=min(2*cost1,cost2); else if(num1==3) ans+=min(3*cost1,min(2*cost2,cost2+cost1)); if(num2==1) ans+=min(cost1,cost2); else if(num2==2) ans+=min(2*cost1,cost2); if(num3==1) ans+=min(cost1,cost2); } cout<<ans; }View Code
G. Perfect Word
题意:给你n个字符串。然后让你构建一个尽可能长的字符串,满足这个字符串的所有子串均在这n个字符串中出现过,输出这个字符串的长度。
思路:毫无疑问,需要构建的这个字符串一定是给定的这n个字符串中较长的某一个。因此对于其中一个符合答案的较长字符串i而言,n个字符串中所有比它短的字符串可以组成它的所有子串集。因此我们可以将字符串按长度从小到大排序,同时用哈希来加速判断。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> using namespace std; #define ll long long #define rg register #define maxn 125450 #define P 131 #define int long long #define INF 0X7F7F7F #pragma GCC optimize(3) #pragma -fcrossjumping #pragma -fdefer-pop #pragma -fmerge-constans #pragma -fthread-jumps #pragma -floop-optimize #pragma -fif-conversion #pragma -fif-conversion2 #pragma -fdelayed-branch #pragma -fguess-branch-probability #pragma -fcprop-registers #pragma -fforce-mem #pragma -foptimize-sibling-calls #pragma -fstrength-reduce #pragma -fgcse #pragma -fcse-follow-jumps #pragma -frerun-cse-after-loop #pragma -fdelete-null-pointer-checks #pragma -fextensive-optimizations #pragma -fregmove #pragma -fschedule-insns #pragma -fsched-interblock #pragma -fcaller-saves #pragma -fpeephole2 #pragma -freorder-blocks #pragma -fstrict-aliasing #pragma -funit-at-a-time #pragma -falign-functions #pragma -fcrossjumping #pragma -finline-functions #pragma -fweb inline int read() { int x=0,f=1; char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c<='9'&&c>='0') { x=(x<<1)+(x<<3)+(c^48); c=getchar(); } return x*f; } inline void write(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) write(x/10); putchar(x%10+'0'); } inline mul(int a,int b) { int sum=1; while(b) { if(b&1) sum=sum*a; a=a*a; b>>=1; } return sum; } int n; struct node { int len; string str; }s[maxn]; inline bool cmp(node a,node b) { return a.len<b.len; } unsigned long long p[maxn],h[maxn]; inline void Hash(string s) { h[0]=s[0],p[0]=1; for(rg int i=1;i<s.length();++i) { h[i]=h[i-1]*P+s[i]; p[i]=p[i-1]*P; } return ; } inline unsigned long long get(int l,int r) { return h[r]-h[l-1]*p[r-l+1]; } map<int,int>mp; int ans; signed main() { n=read(); for(rg int i=1;i<=n;++i) { cin>>s[i].str; s[i].len=s[i].str.length(); } sort(s+1,s+1+n,cmp); for(rg int i=1;i<=n;++i) { Hash(s[i].str); int sum=get(0,s[i].len-1); mp[sum]=1; bool flag=true; for(rg int j=0;j<s[i].len;++j) { for(rg int k=0;k<s[i].len-j;++k) { if(mp[get(k,k+j)]!=1) { flag=false; goto outer; } } } outer:; if(flag==true) ans=max(ans,s[i].len); } cout<<ans; }View Code
J. Strange Sum
题意:给定一个长度为n的序列a。我们可以里面选择至多两个元素,当我们选择ai的时候,下一个元素必须在长度为i的区间里面选择(该区间需包含ai)。求所选的最大元素和。(可以不选)
思路:签到题,枚举第一个选择的元素,第二个就是求区间最大。这里我用的ST表。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> using namespace std; #define ll long long #define rg register #define maxn 425450 #define P 131 #define int long long #define INF 0X7F7F7F #pragma GCC optimize(3) #pragma -fcrossjumping #pragma -fdefer-pop #pragma -fmerge-constans #pragma -fthread-jumps #pragma -floop-optimize #pragma -fif-conversion #pragma -fif-conversion2 #pragma -fdelayed-branch #pragma -fguess-branch-probability #pragma -fcprop-registers #pragma -fforce-mem #pragma -foptimize-sibling-calls #pragma -fstrength-reduce #pragma -fgcse #pragma -fcse-follow-jumps #pragma -frerun-cse-after-loop #pragma -fdelete-null-pointer-checks #pragma -fextensive-optimizations #pragma -fregmove #pragma -fschedule-insns #pragma -fsched-interblock #pragma -fcaller-saves #pragma -fpeephole2 #pragma -freorder-blocks #pragma -fstrict-aliasing #pragma -funit-at-a-time #pragma -falign-functions #pragma -fcrossjumping #pragma -finline-functions #pragma -fweb inline int read() { int x=0,f=1; char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c<='9'&&c>='0') { x=(x<<1)+(x<<3)+(c^48); c=getchar(); } return x*f; } inline void write(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) write(x/10); putchar(x%10+'0'); } int n,a[maxn],ans; int f[maxn][20]; int lg[maxn]; inline void ST_prework() { for(rg int j=1;(1<<j)<=n;++j) { for(rg int i=1;i<=n-(1<<j)+1;++i) { f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]); } } } inline int query(int l,int r) { int k=lg[r-l+1]/(lg[2]); return max(f[l][k],f[r-(1<<k)+1][k]); } signed main() { n=read(); for(rg int i=1;i<=n;++i) { a[i]=read(); f[i][0]=a[i]; } lg[1]=0,lg[2]=1; for(rg int i=3;i<=n+5;++i) lg[i]=lg[i/2]+1; ST_prework(); for(rg int i=1;i<=n;++i) { int temp=0; if(a[i]<=0) continue; int l=1,r=min(n,2*i-1); if(l<=i-1) temp=max(temp,query(l,i-1)); if(r>=i+1) temp=max(temp,query(i+1,r)); ans=max(ans,temp+a[i]); } cout<<ans; }View Code
L. Tree
题意:给你一棵树,需要你把其中所有的节点分成多个集合。集合一共有两类,第一类集合是该集合中的任意两个点满足祖先关系、第二类集合则相反,任意两个点都不满足祖先关系。求最少能分成多少个集合。
思路:可以想象得到,第一类集合大概是长的类似一条链一样的。第二类集合则是多个没关系的叶子节点所组成的。因此,第一类集合和链长有关系,而第二类集合和叶子节点深度有关系。因此我们可以采用长链剖分,将整棵树给分成一条条链,然后将链按长度从大到小进行排序。接着枚举i,前i条链上的所有节点则采用 第一类集合,后面的节点则采用第二类集合。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> using namespace std; #define ll long long #define rg register #define maxn 2025450 #define P 131 #define int long long #define INF 0X7F7F7F #pragma GCC optimize(3) #pragma -fcrossjumping #pragma -fdefer-pop #pragma -fmerge-constans #pragma -fthread-jumps #pragma -floop-optimize #pragma -fif-conversion #pragma -fif-conversion2 #pragma -fdelayed-branch #pragma -fguess-branch-probability #pragma -fcprop-registers #pragma -fforce-mem #pragma -foptimize-sibling-calls #pragma -fstrength-reduce #pragma -fgcse #pragma -fcse-follow-jumps #pragma -frerun-cse-after-loop #pragma -fdelete-null-pointer-checks #pragma -fextensive-optimizations #pragma -fregmove #pragma -fschedule-insns #pragma -fsched-interblock #pragma -fcaller-saves #pragma -fpeephole2 #pragma -freorder-blocks #pragma -fstrict-aliasing #pragma -funit-at-a-time #pragma -falign-functions #pragma -fcrossjumping #pragma -finline-functions #pragma -fweb inline int read() { int x=0,f=1; char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c<='9'&&c>='0') { x=(x<<1)+(x<<3)+(c^48); c=getchar(); } return x*f; } inline void write(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) write(x/10); putchar(x%10+'0'); } int n; struct node { int v,nxt; }s[maxn]; int head[maxn],tot; inline void add(int x,int y) { s[++tot].v=y; s[tot].nxt=head[x]; head[x]=tot; } int hson[maxn],len[maxn];//重儿子 ---- 链长 inline void dfs1(int x)//长链剖分 { // cout<<"x="<<x<<endl; // system("pause"); len[x]=1; for(rg int i=head[x];i;i=s[i].nxt) { int v=s[i].v; dfs1(v); if(len[v]+1>len[x]) { len[x]=len[v]+1; hson[x]=v; } } } int top[maxn];//每个节点所在链的最顶端的节点 inline void dfs2(int x,int topf)//x--当前节点 topf--当前节点所在链的最顶端的节点 { top[x]=topf; if(hson[x]==0) return ;//没有儿子的话就返回 dfs2(hson[x],topf);//这里优先处理重儿子 因为重儿子编号要连续 for(rg int i=head[x];i;i=s[i].nxt) { int v=s[i].v; if(v==hson[x]) continue;//因为处理过重儿子了所以不需要再次dfs下去 dfs2(v,v);//每个轻儿子都有一条以自己开始的链 } } inline void pre_work() { tot=0; for(rg int i=0;i<=n+5;++i) { top[i]=0; hson[i]=0; len[i]=0; head[i]=0; s[i].v=s[i].nxt=0; } } inline void solve() { n=read(); pre_work(); for(rg int i=2;i<=n;++i) { int x=read(); add(x,i); } dfs1(1); dfs2(1,1); vector<int>ans; for(rg int i=1;i<=n;++i) { if(i==top[i]) ans.push_back(len[i]); } sort(ans.begin(),ans.end(),greater<int>()); int temp=ans.size(),cnt=0; for(rg int i=0;i<ans.size();++i) { temp=min(temp,ans[i]+cnt); cnt++; } cout<<temp<<endl; } int t; signed main() { t=read(); while(t--) { solve(); } return 0; }View Code
标签:Contest,int,Regional,Xian,long,while,pragma,inline,define From: https://www.cnblogs.com/sakuya726/p/17660692.html