首页 > 代码库 > Codeforces Round #250 (Div. 2) A B C

Codeforces Round #250 (Div. 2) A B C

2024-07-25 11:22:37   227人阅读

C 贪心 写的时候突然发现这么容易，所有的绳子都要拆掉，而且绳子的个数固定，所以只要每次拆绳子，只要找绳子两端v小的即可，O(n)  //代码里面有没用的冗余

//#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;

#define ls(rt) rt*2
#define rs(rt) rt*2+1
#define ll long long
#define ull unsigned long long
#define rep(i,s,e) for(int i=s;i<e;i++)
#define repe(i,s,e) for(int i=s;i<=e;i++)
#define CL(a,b) memset(a,b,sizeof(a))
#define IN(s) freopen(s,"r",stdin)
#define OUT(s) freopen(s,"w",stdout)
const ll ll_INF = ((ull)(-1))>>1;
const double EPS = 1e-8;
const double pi = acos(-1.0);
const int INF = 100000000;

const int MAXN = 2000*2+100;
vector<int>g[MAXN];
int v[MAXN],id[MAXN];
int n,m;

int main()
{
    //IN("C.txt");
    while(~scanf("%d%d",&n,&m))
    {
        int u,t;
        for(int i=0;i<=n;i++)
            g[i].clear();
        for(int i=1;i<=n;i++)
            scanf("%d",&v[i]),id[i]=i;
        //sort(id+1,id)
        ll ans=0;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&u,&t);
            g[u].push_back(t);
            g[t].push_back(u);
            if(v[t]>v[u])ans+=v[u];
            else ans+=v[t];
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

B---胡蒙的，至今不解为啥按lowbit从大到小一定可以找出sum的组合

//#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;

#define ls(rt) rt*2
#define rs(rt) rt*2+1
#define ll long long
#define ull unsigned long long
#define rep(i,s,e) for(int i=s;i<e;i++)
#define repe(i,s,e) for(int i=s;i<=e;i++)
#define CL(a,b) memset(a,b,sizeof(a))
#define IN(s) freopen(s,"r",stdin)
#define OUT(s) freopen(s,"w",stdout)
const ll ll_INF = ((ull)(-1))>>1;
const double EPS = 1e-8;
const double pi = acos(-1.0);
const int INF = 100000000;

const int MAXN = 1e5+100;

int vis[MAXN],a[MAXN];
int sum,up;

inline int lowbit(int x)
{
    return x&(-x);
}

vector<int>ans;

bool cmp(int ca,int cb)
{
    return lowbit(ca)>lowbit(cb);
}

int main()
{
    //IN("B.txt");
    while(~scanf("%d%d",&sum,&up))
    {
        ans.clear();
        for(int i=0;i<=up;i++)
            a[i]=i;
        sort(a+1,a+1+up,cmp);
        for(int i=1;i<=up;i++)
         {
             int tmp=lowbit(a[i]);
            // printf("i=%d %d\n",i,a[i]);
             /////
             if(sum>=tmp)sum-=tmp,ans.push_back(a[i]);
             if(sum==0)break;
         }
         if(sum!=0)puts("-1");
         else
         {

             printf("%d\n",ans.size());
             if(ans.size())printf("%d",ans[0]);
             for(int i=1;i<ans.size();i++)
                printf(" %d",ans[i]);
             putchar('\n');
         }
    }
    return 0;
}

A  纯属联系string类的substr函数了 不过用String数组写更好些，我的代码冗余严重

//#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;

#define ls(rt) rt*2
#define rs(rt) rt*2+1
#define ll long long
#define ull unsigned long long
#define rep(i,s,e) for(int i=s;i<e;i++)
#define repe(i,s,e) for(int i=s;i<=e;i++)
#define CL(a,b) memset(a,b,sizeof(a))
#define IN(s) freopen(s,"r",stdin)
#define OUT(s) freopen(s,"w",stdout)
const ll ll_INF = ((ull)(-1))>>1;
const double EPS = 1e-8;
const double pi = acos(-1.0);
const int INF = 100000000;

string a,b,c,d;

int checka()
{
    int len=a.size()*2;
    if(len <= b.size() && len <=c.size() && len<=d.size())return 1;
    if(a.size()>=b.size()*2 && a.size()>=d.size()*2 && a.size()>=c.size()*2)return 1;
    return 0;
}
int checkb()
{
    int len=b.size()*2;
    if(len <= a.size() && len <=c.size() && len<=d.size())return 1;
    if(b.size()>=a.size()*2 && b.size()>=d.size()*2 && b.size()>=c.size()*2)return 1;
    return 0;
}

int checkc()
{
    int len=c.size()*2;
    if(len <= a.size() && len <=c.size() && len<=d.size())return 1;
    if(c.size()>=a.size()*2 && c.size()>=d.size()*2 && c.size()>=b.size()*2)return 1;
    return 0;
}

int checkd()
{
    int len=d.size()*2;
    if(len <= a.size() && len <=c.size() && len<=b.size())return 1;
    if(d.size()>=a.size()*2 && d.size()>=c.size()*2 && d.size()>=b.size()*2)return 1;
    return 0;
}

int main()
{
    //IN("A.txt");
    while(cin >> a >> b >> c >> d)
    {
        a=a.substr(2,a.size()-2);
        b=b.substr(2,b.size()-2);
        c=c.substr(2,c.size()-2);
        d=d.substr(2,d.size()-2);

        int flag=0;
        char ans;
        if(checka()){ans='A';flag++;}
        if(checkb()){ans='B';flag++;}
        if(checkc()){ans='C';flag++;}
        if(checkd()){ans='D';flag++;}
        if(flag == 1){printf("%c\n",ans);continue;}
        puts("C");
    }
    return 0;
}


Codeforces Round #250 (Div. 2) A B C


联系
我们