比赛链接:https://vjudge.csgrandeur.cn/contest/536129#problem
难度评测:
codeforces div3前四题。难度最高D题 1400分构造题。洛谷两红两橙。
有两个构造题。难度还可以,需要认真分析一下。不能想的太复杂,这两个题一开始我思路都错了一次,C题是读题错了。这两个构造题应该是codeforces绿蓝名的题。
剩下的题个人感觉F和G题还不错,H作为橙题有点水。校赛更倾向CDFG这种开拓性的题。板子题较少。如果这些题全部没问题,校赛应该能很好地解决百分之七十左右的题。保二争一应该有。ABE有校赛签到水平。
题解:
A:大意是模拟a+b输出a+b的值。
比较简单。scanf格式输入,然后输出即可。
code:
void solve() { int a,b; scanf("%d+%d",&a,&b); cout<<a+b<<endl; }
B:大意是给出一个四格矩阵,可以90度旋转,对于[a,b][c,d]判断是否可以满足a<b ,c<d,a<c,b<d。
四重循环遍历状态。每次交换一下相邻元素。4*90=360。满足一圈
code:
void solve() { int a,b,c,d; cin>>a>>b>>c>>d; for(int i=1;i<=4;i++){ if(a<b&&c<d&&a<c&&b<d){ cyes; return; } int t = c; c=d;d=b;b=a;a=t; } cno; }
C:构造题。大意是给出k和n。找到从1-n中k个数组成的序列满足最大的条件。条件为a[i]-a[i-1]的和。
对于长度符合的构造1,2,3...的差。不符合长度的直接+1输出即可。一开始读题读错了。忘记了应该有序。
code:
void solve() { int k,n; cin>>k>>n; int a= 1; int c= 1; cout<<1<<' '; for(int i=2;i<=k;i++){ if(a+c<=n&&(k-i+(a+c))<=n){ cout<<a+c<<' '; a = a+c; c++; }else{ cout<<a+1<<' '; a++; } } cout<<endl; }
D:构造题。大意是给出一个数组。求是否存在一个x,对于所有(不是任意)是所有。满足a[i] = abs(a[i]-x)。使其数组递增。
这个题最开始分析错了。以为存在单调关系。这个题可以对于所有的逆序a[i],求一个最大的两个数平均值。然后看这个值是否可以满足。
为什么要找两个数的平均的值。因为这个值恰恰使得这两个数可以改变次序。
code:
void solve() { int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } ll maxt = 0; for(int i=2;i<=n;i++){ if(a[i]<a[i-1]){ maxt = max(maxt,upchu((a[i]+a[i-1]),2)); // cout<<maxt<<endl; // cout<<a[i]<<' '<<a[i-1]<<endl; } } for(int i=1;i<=n;i++){ a[i] = abs(a[i]-maxt); if(a[i]<a[i-1]){ cout<<-1<<endl; return; } } cout<<maxt<<endl; }
E题:大意是给出一个数组。去重排序后输出。
我第一个反应是可以拿unique这个函数去重,先排序,然后直接删掉后面的重复。当然这个题应该也可以用哈希表来做。不删的话也可以判断第一个逆序和相等。做法很多
code:
int main() { //cin.ignore(numeric_limits<streamsize>::max(),'\n'); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin>>n; int x; for(int i=1;i<=n;i++){ cin>>x; ve.push_back(x); } sort(ve.begin(),ve.end()); ve.erase(unique(ve.begin(),ve.end()),ve.end()); cout<<ve.size()<<endl; for(int i=0;i<ve.size();i++){ cout<<ve[i]<<' '; } cout<<endl; }
F题:大意是给出一个数n,求n!的质因子。对数量进行排序后输出cnt+质因子。
比较简单。第一个思路来的很快,因为map可以直接排序。保险起见,线性筛一遍质数ans边记录边除质因子,map进行存储,直接迭代器输出。这样做法应该是比较保守的。复杂度差不多nlogn。又是保险起见,因为这个算法跑的比较快。n我筛了一个大范围n*10.即使这样跑出来也就是几十ms。
code:
const int nn = 100010; bool sign[nn]; vector<int> ve; map<int,int> mp; void shai(){ for(int i=2;i<nn;i++){ if(!sign[i]) ve.push_back(i); for(int j=2;i*j<nn;j++){ sign[i*j] = true; } } } int main() { //cin.ignore(numeric_limits<streamsize>::max(),'\n'); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); shai(); ll n; cin>>n; ll ans = 1; for(int i=1;i<=n;i++){ ans *=i; for(int j=0;j<ve.size();j++){ if(ve[j]>ans) break; else{ while(ans%ve[j]==0) ans/=ve[j],mp[ve[j]]++; } } } map<int,int>::iterator it = mp.begin(); while(it!=mp.end()){ cout<<it->fi<<' '<<it->se<<endl; it++; } }
G题:大意是给出一个x和y,求p,q满足gcd是x最小公倍数是y的数量。
分情况讨论。如果x<y是0,x=y是1.其他的就找满足的数量,然后翻个倍数。中间具体怎么操作?
如果pq满足是x的倍数。那么p一定可以由x乘以一个倍数。q一定可以由y除以一个倍数。前提是y%x=0。如果不等于也不要紧,因为if我们可以再判断一下。if里面我们直接判断题目中的条件即可。
code:
int main() { //cin.ignore(numeric_limits<streamsize>::max(),'\n'); //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int x,y; cin>>x>>y; int a,b; int ans = 0; for(int i=1;i<=y/x;i++){ a = x*i; b = y/i; if(a>b) break; if(__gcd(a,b)==x&&a*b/__gcd(a,b)==y) ans++; } if(x==y) cout<<1<<endl; else if(x>y) cout<<0<<endl; else cout<<ans*2<<endl; }
H题:01背包板子题。大意是给出总钱数和m个商品。求购买的总价值。每个商品的价值等于 价格*价值系数。
正常跑一遍01背包。状态表示将+value[i]替换为+money[i]*value[i],难度较低。
code:
int main() { //cin.ignore(numeric_limits<streamsize>::max(),'\n'); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m; cin>>n>>m; for(int i=1;i<=m;i++){ cin>>money[i]>>value[i]; } for(int i=1;i<=m;i++){ for(int j=0;j<=n;j++){ if(j<money[i]) f[i][j] = f[i-1][j]; else f[i][j] = max(f[i-1][j],f[i-1][j-money[i]]+money[i]*value[i]); } } cout<<f[m][n]; }