赛后练习,慢慢找感觉
A要考虑很多种情况,特别是坐m站路车的距离大于n但是更便宜的情况
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int n,m,a,b; int main(){ while(cin>>n>>m>>a>>b){ int x=a*m; if(x<b){ cout<<a*n<<endl; }else{ int res=0; if(m>n){ if(b>n*a){ res=n*a; }else{ res=b; } }else{ res+=(n/m*b); res+=n%m*a; res=min(res,n/m*b+b); } cout<<res<<endl; } } return 0; }
B,贪心思路,从6*n开始向上枚举房间的面积,存在符合的则输出,注意要用int64
#include<iostream>#include<cstring>#include<cstdio>#include<cmath>usingnamespace std;longlong n,a,b;int inprim(longlong aaa,longlong&beg,longlong&edd){longlong i;longlong k=sqrt(aaa);for(i=beg;i<=k;i++){if(aaa%i==0&&aaa/i>=edd){ beg=i; edd=aaa/i;return i;}}return-1;}int main(){while(scanf("%I64d",&n)!=EOF){ scanf("%I64d%I64d",&a,&b);if(n*6<=a*b){ printf("%I64d\n",a*b); printf("%I64d %I64d\n",a,b);continue;} n*=6;longlong res;while(1){longlong edd=max(a,b);longlong beg=min(a,b);longlong flag=inprim(n,beg,edd);if(flag!=-1){ res=beg*edd;if(a<=beg){ a=beg,b=edd;}else{ b=beg,a=edd;}break;} n++;} printf("%I64d\n",res); printf("%I64d %I64d\n",a,b);}return0;}
C,比B要水,遍历两遍即可
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int num[600000],n,dp[600000]; int main(){ int i; long long sum,res; while(scanf("%d",&n)!=EOF){ res=sum=0; for(i=1;i<=n;i++){ scanf("%d",&num[i]); sum+=num[i]; } if(sum%3!=0){ printf("0\n"); continue; } sum/=3; memset(dp,0,sizeof(dp)); long long suml=0,sumr=0; for(i=n;i>0;i--){ sumr+=num[i]; dp[i]=dp[i+1]; if(sumr==sum){ dp[i]++; } } for(i=1;i<n;i++){ suml+=num[i]; if(suml==sum){ res+=dp[i+2]; } } // for(i=1;i<=n;i++)cout<<dp[i]<<" "; // cout<<endl; printf("%I64d\n",res); } return 0; }
D 没看懂样例,留着坑回来填
E 并查集的好题,题意是给出一些人和他上司的关系图,第a个人知道第i条消息后,这个人的上司以及上司的上司都会知道这个消息。在线的询问,第x人知不知道第k条消息
这题技巧在于,每次都记录知道第i条消息人关系链的头和尾,输入第x个人和第i条消息后,看他是不是在第i条消息关系链的头和尾上即可。
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int nMax=100005; int father[nMax],boss[nMax]; int find(int x){ // 寻找父节点 if(x!=father[x]) return father[x]=find(father[x]); return x; } void init(){ // 初始化 int i; for(i=0; i<nMax-1; i++){ boss[i]=father[i]=i; } } int vv1[nMax],vv2[nMax]; int main(){ int n,m,a,b,c,nk; while(scanf("%d%d",&n,&m)!=EOF){ init(); nk=1; while(m--){ scanf("%d",&a); if(a==1){ scanf("%d%d",&b,&c); boss[b]=c; father[b]=c; }else if(a==2){ scanf("%d",&b); vv1[nk]=b; vv2[nk++]=find(b); //第nk条信息由第b人穿到第findb人 }else if(a==3){ scanf("%d%d",&b,&c); //第b个人,第c条信息 bool flag=0; int beg=vv1[c]; int edd=vv2[c]; //第c条消息的开始和结束 while(true){ if(beg==b){ flag=1; break; }if(beg==edd){ break; } beg=boss[beg]; } if(flag){printf("YES\n");} else printf("NO\n"); } } } return 0; }
相关推荐
Codeforces Round #723 (Div. 2).md
上面代码跑出来的dp[n][m]是0,然后从(1,1)(1,2)(2,2)(2,3)这样的相与值是k (看懂ans+k是啥应该就懂了) 代码: int main() { std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int ans=(1&...
传送门 题意: 开始位置在0,问能否跳到n+1位置 每步只能跳d 在1——n每个位置有方向,L,R,求d的最小值 思路: 只用找相邻两个R之间的最大值即可 代码: #include #include ...typedef long long l
就是把所有相等的数放到一个vector里,如果他出现大于2次,看最远的间距是否大于2即可,找到一个就可以 代码: #include #include #include #include #include #include #include #include #include #include #...
长度为n的字符串包含n−2n−2n−2个aaa和222个bbb,求按照字典序排列输出第kkk个字符串 解题思路 第一个bbb在倒数第二位有1个字符串,在倒数第三位有2个字符串…在倒数第nnn位时有n−1n-1n−1个字符串 可以根据第一...
E. Cyclic Components 题目链接-E. Cyclic Components 题目大意 给你nnn个点和mmm条边,求所构成图中单圈环的个数 ...并查集并查集并查集 很明显单圈环每个点的度都为222,所以我们可以用数组cnt[]记录每个点的度,...
Codeforces Round #629 (Div. 3) E.Tree Queries (DFS) 思路:若ai 在路径上 ,则ai的父结点一定在路径上,若ai是路径上某个结点的子结点,则ai的父结点一定在路径上,综上只需考虑ai的父节点就行了。对每个ai判断...
给两两节点放一个数字(0~n-2 唯一) 给你一棵树,求所有任意两节点相连的路以外的路上的数字的最小值最小 思路 构造 若一个点连了三条边及以上,则这个点的边从最小值开始赋值。其他边从最大点开始赋值。 证明:一...
给一个长度为n的数组,两种操作,一个是把任意一个ai变成ai+2a_i变成a_i+2ai变成ai+2,另一个是如果所有数都大于0,可以把所有数减1,问通过这些操作能否把所有数变为0 思路: 如果任意两个数之差为奇数,那么就...
输入一个正整数x,找出这样的2个正整数a和b,使得gcd(a,b)+lcm(a,b)=x 解题思路 找最特殊的情况a=1,b=x-1即可 这样a,b两个数最大公因数为1,最小公倍数x-1,满足题意√ 附上代码 #include #define int long long #...
B. Longest Palindrome time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Returning back to problem solving, Gildong is now studying about ...
将所有数字看成2进制,从最高位看起,如果第i位上为1的数只有一个的话,那么这个数必然对答案有贡献,就把它排在第一个,后面任意排。 例:11,6,4,0 二进制表示为:1011,110,100,0 右起第四位为1的只有1011,...
传说门 刚好今晚是中国场! 其实这道题比较水,但当时思路错,一心想着化简公式,浪费了好多时间a....#pragma GCC optimize(2) #include #define ll long long #define endl '\n' using namespace std; const int manx=
C(n-2,i-1)*C(j-1,n-2)*(i-1) __ j: n-1 -> m 我们发现内层循环,每次只是j加一,我们就可以只用一次组合数剩下的用差量表示 对于外层循环同理 只有(i-1) * C(n-2,i-1) i会每次加一。我们也只算一次剩下的用差量...
传送门 题意: 找规律,题意就是有多少种方式填充该图形 画两个就发现,输出n即可 代码: #include #include #include #include #include #include #include #include ...#define SZ(x) ((int)(x)
A #include using namespace std; typedef long long ll; int main(){ int t; cin>>t; while(t--){ ll x; cin>>x; cout<<1>>t; while(t--){ st.clear(); ll n; cin >>n;... ll re
题目链接:B. Longest Palindrome 题目 Returning back to problem solving, Gildong is now studying about palindromes. He learned that a palindrome is a string that is the same as its reverse....
惭愧,前几天刚学的dfs序判祖先关系都忘了用。。 这题我们先把所有点都变成父亲节点(根节点不变),这样只需要判所有节点是否在一条链上。 由于判断x是y的祖先:需要满足:st[x]<...const int M = 2e5+