首页 > 代码库 > CF 725C 模拟 725D

CF 725C 模拟 725D

CodeForces 725C

题意:长27的字符串,26个英文字母至少出现了一次。这个字符串是由两行13列的字符相邻行走得来,求这个两行13列的字符。

题解:思路很好想,找其中两个一样的字符,间距d,平分到两行。  注:以后写草稿要写清楚点。。被自己坑死了。。

技术分享
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define FF(i,a,b) for (int i=a;i<=b;i++)#define F(i,b,a)  for (int i=b;i>=a;i--)#define mes(a,b)  memset(a,b,sizeof(a))#define INF 0x3f3f3f3ftypedef long long ll;const int N = 2e5+10;int main(){    string s;    char s1[50], s2[50];    cin>>s;    int a, b;    FF(i,0,26) FF(j,0,i-1)        if(s[i]==s[j])  a=j, b=i;    int i, j, x=b-a, y=(x+1)/2;    if(x==1) { puts("Impossible"); return 0; }    for(i=12-y+1,j=a; i<=12; i++,j++) s1[i]=s[j];    for(i=12; j<b; i--,j++) s2[i]=s[j];    for(j=b+1; i>=0&&j<=26; i--,j++) s2[i]=s[j];    if(j==27) {        for(j=0; i>=0&&j<a; i--,j++) s2[i]=s[j];        for(i=0; j<a; i++,j++) s1[i]=s[j];    }    else {        for(i=0; j<=26; i++,j++) s1[i]=s[j];        for(j=0; j<a; i++,j++) s1[i]=s[j];    }    s1[13]=s2[13]=\0;    cout<<s1<<endl<<s2<<endl;    return 0;}
View Code

 CodeForces 725D

题意:n个人,每人有ti个气球,wi重量。当ti>wi时,他飞走。按最后留下的人的气球数量排名,第一个人可以把气球给其它人,求第一个人最后尽可能高的排名。

题解:一开始总想怎么排序,应该把握好关键点,就是每次找到可以放飞且给出气球数量最少的人即可。所以用个优先队列就好了。把所有比第一个人气球多的人加入队列,队列内部按要增加的气球数排序。每次把队列中首个人放飞,这时候要继续往队列中加人,同时比较一下答案,直到不能放飞为止。

技术分享
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define FF(i,a,b) for (int i=a;i<=b;i++)#define F(i,b,a)  for (int i=b;i>=a;i--)#define mes(a,b)  memset(a,b,sizeof(a))#define INF 0x3f3f3f3ftypedef long long ll;const int N = 3e5+10;struct P{    ll ti, wi, ci;    friend bool operator < (const P & a, const P &b) {        return a.ci>b.ci;    }}p[N];int n, ans;ll t1, w1, s[N];priority_queue<P >A;bool cmp(P a, P b){    return a.ti<b.ti;}int main(){    scanf("%d", &n);    scanf("%lld%lld", &t1, &w1);    FF(i,2,n) {        scanf("%lld%lld", &p[i].ti, &p[i].wi);        p[i].ci=p[i].wi-p[i].ti+1;        if(p[i].ti>t1) A.push(p[i]);    }    sort(p+2, p+1+n, cmp);    for(int i=2; i<=n; i++)  s[i]=p[i].ti;    ans=A.size()+1;    ll l=upper_bound(s+2, s+1+n, t1)-s, r;    while(true) {        if(A.empty()) { printf("%d\n", ans); return 0; }        if(A.top().ci<=t1) {            P st=A.top();  A.pop();            r=l, l=upper_bound(s+2, s+1+n, t1-st.ci)-s;            for(int i=r-1; i>=l; i--) {                A.push(p[i]);            }            int m=A.size()+1;            t1-=st.ci;            if(ans>A.size()+1) ans=A.size()+1;        }        if(A.top().ci>t1) { printf("%d\n", ans); return 0; }    }    return 0;}
View Code

CF 725C 模拟 725D