首页 > 代码库 > Codeforces Round #FF(255) (Div. 2)
Codeforces Round #FF(255) (Div. 2)
A题
/*ID: neverchanjePROG:LANG: C++11*/#include<vector>#include<iostream>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<cstdio>#include<set>#include<queue>#include<map>using namespace std;#define INF 0Xfffffff#define maxntypedef long long ll;typedef pair<int,int> pii;typedef vector<int,int> vii;int p,n;bool h[301];int a[301];int main(){// freopen("a.txt","r",stdin);// freopen(".out","w",stdout); while(cin>>p>>n){ int x;bool find=0; memset(h,0,sizeof(h)); for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++){ if(h[a[i]%p]){ cout<<i<<endl; find=1; break; } else h[a[i]%p]=1; } if(!find)puts("-1"); } return 0;}/*DESCRIPTION:*/
B题 贪心
/*ID: neverchanjePROG:LANG: C++11*/#include<vector>#include<iostream>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<cstdio>#include<set>#include<queue>#include<map>using namespace std;#define INF 0Xfffffff#define maxntypedef long long ll;typedef pair<int,int> pii;typedef vector<int,int> vii;char s[1001];int k;int h[27];int main(){// freopen("a.txt","r",stdin);// freopen(".out","w",stdout); while(cin>>s){ cin>>k; int m=-1; for(int i=0;i<26;i++){ cin>>h[i]; if(h[i]>m) m=h[i]; } ll ans=0;int l=strlen(s); for(int i=0;i<l;i++) ans+=h[s[i]-‘a‘]*(i+1); ans+=(l+1+l+k)*k*m/2; cout<<ans<<endl; } return 0;}/*DESCRIPTION:*/
C题 dp
/*ID: neverchanjePROG:LANG: C++11*/#include<vector>#include<iostream>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<cstdio>#include<set>#include<queue>#include<map>using namespace std;#define INF 0Xfffffff#define maxn 100001typedef long long ll;typedef pair<int,int> pii;typedef vector<int,int> vii;int n,a[maxn],s[maxn],e[maxn];int main(){// freopen("a.txt","r",stdin);// freopen(".out","w",stdout); while(cin>>n){ for(int i=1;i<=n;i++) cin>>a[i]; s[n]=1; for(int i=n-1;i>=1;i--) s[i] = (a[i]<a[i+1])? s[i+1]+1 : 1; e[1]=1; for(int i=2;i<=n;i++) e[i] = (a[i]>a[i-1])? e[i-1]+1 : 1; int ans = max( e[n-1]+1 , s[2]+1 ); for(int i=2;i<=n-1;i++){ if(a[i+1] - a[i-1]>1) ans = max( ans , e[i-1]+s[i+1]+1 ); else ans = max(ans , max(s[i+1],e[i-1])+1 ); } cout<<ans<<endl; } return 0;}/*DESCRIPTION:题还是做得太少,这题跟lis一点关系都没有以i为开头的最长连续序列s[i],以i为结尾的最长连续序列e[i]这题恶心,按理来说ai>0,但是数据允许你把ai改成0*/
D题 优先队列
/*ID: neverchanjePROG:LANG: C++11*/#include<vector>#include<iostream>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<cstdio>#include<set>#include<queue>#include<map>using namespace std;#define INF 1e9#define maxn#define rep(i,x,y) for(int i=x;i<=y;i++)#define mset(x) memset(x,0,sizeof(x))typedef long long ll;typedef pair<int,int> pii;typedef vector<int,int> vii;int n,m,k,p;int row[1001],col[1001];ll sc[1000000],sr[1000000];int main(){// freopen("a.txt","r",stdin);// freopen(".out","w",stdout); cin>>n>>m>>k>>p; mset(row);mset(col); int x; rep(i,0,n-1) rep(j,0,m-1){ cin>>x; row[i]+=x; col[j]+=x; } priority_queue<int> c,r; rep(i,0,m-1) c.push(col[i]); rep(i,0,n-1) r.push(row[i]); sc[0]=0;sr[0]=0; rep(i,1,k){//把最大的k列存进c中 int x=c.top() , y=r.top(); sc[i] = sc[i-1]+x; sr[i] = sr[i-1]+y; c.pop(); r.pop(); c.push(x-n*p); r.push(y-m*p); } ll ans = sr[k]; rep(i,1,k){ ans = max( ans, sc[i]+sr[k-i]-1ll*(k-i)*i*p ); } cout<<ans<<endl; return 0;}/*DESCRIPTION:按照某种取法得到解,解与行列选择的顺序无关取了i列,(k-i)行ans = max( sigma(col) + sigma(row) - (k-i)*i*p )将col和row分别用priority_queue储存枚举i,意味着要把最大的k个列存进prq中由于i列中可能会有重复的算法就是:先在prq中找最大col, 把col-n*p存进去,如此循环k次这样prq里有了最大的k个数不过这样占用的内存过大要及时删除由于最大会有1e12的数,故注意要用long longpriority_queue.top()默认返回最大值*/
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。