NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2016高中組決賽
 H.吃吃為吃吃,是吃也

作者 主題: H.吃吃為吃吃,是吃也  (閱讀 246 次)

darry140

  • 初級會員
  • **
  • 文章數: 32
    • 檢視個人資料
H.吃吃為吃吃,是吃也
« 於: 六月 18, 2017, 05:44:54 pm »

代碼: [選擇]
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,a,b) for(int i=(a);i<=(b);i++)
#define mkp make_pair
#define pb push_back
#ifdef darry140
#define debug(...) do{\
fprintf(stderr,"%s - %d : (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
_DO(__VA_ARGS__);\
}while(0)
template<typename I> void _DO(I&&x){cerr<<x<<endl;}
template<typename I,typename...T> void _DO(I&&x,T&&...tail){cerr<<x<<", ";_DO(tail...);}
#else
#define debug(...)
#endif
//}}}
int n;
vector<pii> ops;
void read()
{
int q;
scanf("%d",&n);
#if 1
scanf("%d",&q);
while(q--)
{
int x;
char s[23];
scanf("%s%d",s,&x);
int msk=0;
REP(i,n) msk|=(int)(s[i]-'0')<<i;
ops.pb(mkp(msk,x));
}
#else
REP1(i,1,(1<<n)-1) if(__builtin_popcount(i)<=8)
ops.pb(mkp(i,100));
debug(SZ(ops));
#endif
}
int w[1<<22];
void doo(int l,int r,vector<pii>::iterator ptl,vector<pii>::iterator ptr)
{
//debug(l,r);
if(l==r-1)
{
for(auto it=ptl;it!=ptr;it++) w[l]+=it->S;
return;
}
int mid=(l+r)/2;
{
auto it=lower_bound(ptl,ptr,mkp(mid,-1000));
doo(l,mid,ptl,it);
doo(mid,r,it,ptr);
}
REP1(i,mid,r-1) w[i]+=w[i-mid+l];
}
void build()
{
sort(ALL(ops));
doo(0,1<<n,ops.begin(),ops.end());
}
void sol()
{
sort(w+1,w+(1<<n));
ll ans=0;//long long ans=0;
REP1(i,1,(1<<n)-1) ans+=(long long)(i)*w[i];
cout<<ans<<endl;//printf("%lld\n",ans);
}
int main()
{
read();
build();
sol();
return 0;
}
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 225
    • 檢視個人資料
Re: H.吃吃為吃吃,是吃也
« 回覆 #1 於: 十一月 07, 2017, 01:22:27 pm »

感謝你提供這麼多題目的解法,
可以的話,請你以後再多幾行文字的敘述,
描述一下解題的重點,
對其他使用者來說應該是會更有幫助。
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2016高中組決賽
 H.吃吃為吃吃,是吃也