Codeforces Round #615 (Div. 3) 题解
overrate_wsj 人气:1A - Collecting Coins
题意:
给你四个数a,b,c,d,n.问你是否能将n拆成三个数A,B,C,使得A+a=B+b=C+c。
思路:
先计算三个数的差值的绝对值abs,如果abs大于n则肯定不行,如果小于n,还需判断(n-abs)%3是否为0,不为0则不行。
#include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<vector> #include<stack> #include<queue> #include<map> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; ll max(ll a,ll b) {if(a>b) return a;return b;} int main() { int t; scanf("%d",&t); while(t--){ int a[3],n; scanf("%d%d%d%d",&a[0],&a[1],&a[2],&n); sort(a,a+3); int x=(a[2]-a[1])*2+a[1]-a[0]; if(x>n) cout<<"NO"<<endl; else{ if((n-x)%3) cout<<"NO"<<endl; else cout<<"YES"<<endl; } } return 0; }
B - Collecting Packages
题意:
给出直角坐标系中的一些坐标,你只能向上('U')或向右('R')走,问你能否走完这些坐标,如果能请输出字典序最小的行进路线
思路:
直接按x坐标排序,如果有一个点的纵坐标在上一个点的纵坐标下方,则无法走。输出顺序只需要从上一个点先走R再走U走到下一个点即可
#include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<vector> #include<stack> #include<queue> #include<map> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; ll max(ll a,ll b) {if(a>b) return a;return b;} const int maxn=1005; struct node{ int x,y; }a[maxn]; int cmp(node a,node b) { if(a.x==b.x) return a.y<b.y; return a.x<b.x; } int main() { int t,n; scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d%d",&a[i].x,&a[i].y); sort(a,a+n,cmp); int flag=0; for(int i=1;i<n;i++){ if(a[i].y<a[i-1].y){ cout<<"NO"<<endl; flag=1; break; } } if(!flag){ cout<<"YES"<<endl; for(int i=0;i<a[0].x;i++) cout<<"R"; for(int i=0;i<a[0].y;i++) cout<<"U"; for(int i=1;i<n;i++){ for(int j=a[i-1].x;j<a[i].x;j++) cout<<"R"; for(int j=a[i-1].y;j<a[i].y;j++) cout<<"U"; } cout<<endl; } } return 0; }
C - Product of Three Numbers
题意:
给你一个数n,问你是否能将n分解成三个不同的数相乘,可以的话则输出任一解
思路:
只需要将遍历从2到,如果i为n的因子,就将i记录,并将n除以i。这样的操作执行三次之后,就可以跳出循环。
如果此时的x不等于1或者循环结束后x不为1,则将x放入数组的尾部,或者将数组的最后一个元素乘上x。
如果最后数组的元素小于3那么则不行,如果等于3的话还需判断一下,三个因数是否相同。
#include<iostream> #include<algorithm> #include<cstring> #include<vector> using namespace std; vector<int> a; typedef long long ll; int main() { int n,t; scanf("%d",&t); while(t--){ int cnt=0; a.clear(); scanf("%d",&n); for(ll i=2;i*i<=n;i++){ if(n%i==0){ a.push_back(i); cnt++; n/=i; } if(cnt==3) break; } if(n!=1){ if(a.size()==3) a.back()*=n; else a.push_back(n); } if(a.size()<3) cout<<"NO"<<endl; else{ if(a[0]==a[1]||a[1]==a[2]||a[0]==a[2]) cout<<"NO"<<endl; else cout<<"YES"<<endl,cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl; } } return 0; }
加载全部内容