程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 2460: [BeiJing2011]元素|線性基|高斯消元|貪心淺析

2460: [BeiJing2011]元素|線性基|高斯消元|貪心淺析

編輯:關於C++

貪心從大到小加入,正確性不是很會證,需要用到擬陣來證明
總之做法就是從大到小貪心加入,如果不與已選的元素沖突,那麼就貪心選他

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define N 1005
using namespace std;
ll sc()
{
    ll i=0; char c=getchar();
    while( c>'9' || c<'0' ) c=getchar();
    while( c>='0' && c<='9' )i=i*10+c-'0',c=getchar();
    return i;
}
struct W{int x;ll a;}a[N];
ll ins[66],ans;
int n;
bool cmp(W a,W b)
{
    return a.x>b.x;
}
int main()
{
    n=sc();
    for(int i=1;i<=n;i++)
        a[i].a=sc(),a[i].x=sc();
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        for(int k=65;k>=0;k--)
        {
            if((a[i].a>>k)&1)
            {
                if(!ins[k])
                {
                    ins[k]=a[i].a;
                    break;
                }
                a[i].a^=ins[k];
            }
        }
        if(a[i].a)ans+=a[i].x;
    }
    cout<
   
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved