这里总结一下codeforces的题目类型:
题目 | 做法练法 |
---|---|
A 简单思维 | 考察见多识广和反应的能力 几乎读题出答案 |
B 规律推导 | 不仅仅需要多观察上几个样例 必须自己从小到大一下 规律一般很明显 |
C 巧妙模拟 | 条件较多的模拟,分类不恰当容易写不出来,有窍门 |
D 简单dp | 动态规划的简单题目 多练很简单 因为规定了算法 甚至要比1 2题目简单 |
C
easy:让一个数字尽可能地大,然后让他来改变全局的递增递减性质
(这个考场上完全想到了,但是没有写出来,实在是可惜可惜) 但是对于c题做了不少了,可以发现基本上来说就是一点思维稍微高点的题目,或者说情况多一点的模拟题目 d题一般是dp这样的题目,都不算很复杂,关键就是见得多了就好了:
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;typedef pair<int,int> PII;
const int N=25;
const int inf=0x3f3f3f3f;
int a[N];signed main(){IOS;int T; cin>>T;while(T--){vector<PII> v;int n,nmax=-inf,dn,nmin=inf,xn,ans=0; cin>>n;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]>nmax){dn=i;nmax=a[i];}if(a[i]<nmin){xn=i;nmin=a[i];}}if(abs(nmax)>abs(nmin)){for(int i=2;i<=n;i++){while(a[i]<a[i-1]){a[i]+=nmax;ans++;v.push_back({i,dn});if(a[i]>nmax){dn=i;nmax=a[i];}}}}else{for(int i=n-1;i>0;i--){while(a[i]>a[i+1]){a[i]+=nmin;ans++;v.push_back({i,xn});if(a[i]<nmin){xn=i;nmin=a[i];}}}}cout<<ans<<'\n';for(auto u:v){cout<<u.first<<' '<<u.second<<'\n';}}return 0;
}
D感觉像是一个背包问题:
#include<bits/stdc++.h>
using namespace std;
bitset<200001>dp;
main(){int n;cin>>n;dp[0]=1;int64_t t=0,ans=0;for(int i=0;i<n;i++){if(t<i)break;int64_t a;cin>>a;t+=a;if(dp[i])ans=max(ans,t-i);dp|=dp<<a;dp[i]=0;}for(int i=n-1;i<200001;i++)if(dp[i]){ans=max(ans,t-i);break;}cout<<ans;
}