NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃
 最新文章
頁: [1] 2 3 ... 10
 1 
 於: 六月 18, 2017, 05:44:54 pm 
作者 darry140 - 最新文章 由 darry140
代碼: [選擇]
#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;
}

 2 
 於: 六月 18, 2017, 05:43:59 pm 
作者 darry140 - 最新文章 由 darry140
代碼: [選擇]
#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
//}}}
const int maxn=517;
int n,r;
//#define TEST
vector<int> in;
void read()
{
scanf("%d%d",&n,&r);
#ifdef TEST
in.resize(n);
for(auto &x:in) cin>>x;
#endif
}
void build()
{
srand(time(0));
}
vector<int> bas;
ll guess(vector<int> v)
{
assert(SZ(v)==n);

REP(i,n) v[i]=(v[i]+bas[i])%r+1;
REP(i,n) printf("%d%c",v[i]," \n"[i==n-1]);
fflush(stdout);
#ifndef TEST
ll x;scanf("%lld",&x);
if(x==0) exit(0);
return x;
#else
ll ret=0;
REP(i,n) ret+=min(abs(v[i]-in[i]),r-abs(v[i]-in[i]));
if(ret==0) exit(0);
return ret;
#endif
}
void sol()
{
REP(i,n) bas.pb((1LL*abs(rand())%r)+1);

vector<int> v(n,1);
vector<int> ans(n);
ll head=guess(v);
if(r%2==1)
{
REP(i,n)
{
vector<int> nv=v;
nv[i]=r/2+1;
auto cur=guess(nv);
auto dlt=cur-head;
dlt+=r/2;
if(dlt%2==0) ans[i]=r/2+1-dlt/2;
else ans[i]=r/2+1+(dlt+1)/2;
}
guess(ans);
assert(0);
}
else
{
REP(i,n-1)
{//bas!!!
vector<int> nv=v;
nv[i]=r/2+1;
auto cur=guess(nv);
auto dlt=cur-head;
dlt=(dlt+r/2)/2;
if(dlt==0) ans[i]=r/2+1;
else if(dlt==r/2) ans[i]=1;
else
{
nv[i]=2;
auto c2=guess(nv);
auto d2=c2-head;
if(d2==1) ans[i]=r/2+1+dlt;
else ans[i]=r/2+1-dlt;
}
}
ll dis=head;
REP(i,n-1) dis-=min(ans[i]-1,r-ans[i]+1);
if(dis==0) ans[n-1]=1;
else if(dis==r/2) ans[n-1]=r/2+1;
else
{
vector<int> nv=v;nv[n-1]=2;
auto c2=guess(nv);
auto d2=c2-head;
if(d2==1) ans[n-1]=r-dis+1;
else ans[n-1]=1+dis;
}
}
guess(ans);
assert(0);
}
int main()
{
read();
build();
sol();
return 0;
}

 3 
 於: 六月 18, 2017, 05:43:26 pm 
作者 darry140 - 最新文章 由 darry140
代碼: [選擇]
#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
//}}}
const int MOD=1e9+7;
inline int add(const int &i,const int &j){return i+j<MOD?i+j:i+j-MOD;}
inline int mul(const int &i,const int &j){return 1LL*i*j%MOD;}
template<size_t maxn>
struct M
{
int dat[maxn][maxn];
M(){memset(dat,0,sizeof(dat));}
M<maxn> operator *(const M<maxn> &x) const
{
M<maxn> ret;
REP(i,maxn) REP(j,maxn) REP(k,maxn)
ret.dat[i][k]=add(ret.dat[i][k],mul(dat[i][j],x.dat[j][k]));
return ret;
}
};
int q;
void read()
{
scanf("%d",&q);
}
M<4> X;
M<3> Y;
void build()
{
vector<int> v{3,1,0,0, 0,0,1,0, MOD-3,0,0,1 ,1,0,0,0};
auto it=v.begin();
REP(i,4) REP(j,4) X.dat[i][j]=*(it++);

v=vector<int>{2,1,0, 0,0,1, MOD-1,0,0};
it=v.begin();
REP(i,3) REP(j,3) Y.dat[i][j]=*(it++);
//n<=3
}
template<typename T>
T powmod(T mat,ll b)
{
assert(b);
if(b==1) return mat;
auto tmp=powmod(mat,b/2);
tmp=tmp*tmp;
if(b&1) tmp=tmp*mat;
return tmp;
}
ll a(ll x)
{
if(x<=3) return vector<int>{0,1,2,6}[x];
else
{
M<4> sub=powmod(X,x-3);
vector<int> v{6,2,1,0};
int ans=0;
REP(i,4) ans=add(ans,mul(v[i],sub.dat[i][0]));
return ans;
}
}
ll b(ll x)
{
if(x<=2) return vector<int>{0,1,2}[x];
else
{
M<3> sub=powmod(Y,x-2);
vector<int> v{2,1,0};
int ans=0;
REP(i,3) ans=add(ans,mul(v[i],sub.dat[i][0]));
return ans;
}
}
void sol()
{
while(q--)
{
ll l,r;scanf("%lld%lld",&l,&r);
ll ans=0;
ans+=a(r);
ans-=a(l-1);
ans-=b(r);
ans+=b(l-1);
debug(a(r),a(l-1),b(r),b(l-1),r,l-1);
ans=ans%MOD*(MOD-MOD/2)%MOD;
if(ans<0) ans+=MOD;
printf("%lld\n",ans);
}
}
int main()
{
read();
build();
sol();
return 0;
}

 4 
 於: 六月 18, 2017, 05:42:19 pm 
作者 darry140 - 最新文章 由 darry140
代碼: [選擇]
#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
//}}}
const int maxn=1e2+2;
int n,m;
void read()
{
cin>>n>>m;
}
int mem[maxn][maxn];
int dp(int x,int y)
{
if(x<=0||y<=0) return 1e7;
if(x>y) swap(x,y);
if(x==y) return 1;

if(~mem[x][y]) return mem[x][y];
int ans=1e7;
REP1(i,1,x-1) ans=min(ans,dp(i,y)+dp(x-i,y));
REP1(j,1,y-1) ans=min(ans,dp(x,j)+dp(x,y-j));
return mem[x][y]=ans;
}
void build()
{
memset(mem,-1,sizeof(mem));
}
void sol()
{
printf("%d\n",dp(n,m));
}
int main()
{
read();
build();
sol();
return 0;
}

 5 
 於: 六月 18, 2017, 05:41:46 pm 
作者 darry140 - 最新文章 由 darry140
代碼: [選擇]
#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
//}}}
const int maxn=1e6+6;
int T;
string A,B;
void read()
{
scanf("%d",&T);
static char in[maxn];
scanf("%s",in);A=in;
scanf("%s",in);B=in;
}
void build()
{

}
inline int d(char c){return 'S'-c-(c=='P');}
ll s[3][maxn];
void doo(ll *opt,int t,ll st,ll rnd,int n)
{
ll ed=st+rnd,edp=(ed-1)%n+1;
const int ful=(ed-1)/n-(st-1)/n;

REP(i,3)
{
const int z=(t+2-i)%3;
opt[i]+=ful*s[z][n]+s[z][edp-1]-s[z][st-1];
}
}
void calc(ll *opt,const string &a,const string &b,int rnd)
{
assert(__gcd(SZ(a),SZ(b))==1);
vector<int> re;
for(int i=0,_=1;_<=SZ(b);_++,i=(i+SZ(a))%SZ(b))
{
int t=d(b[i]);
REP(j,3) s[j][_]=s[j][_-1];
s[t][_]++;
re.pb(i);
}
vector<int> pos(SZ(re));
REP(i,SZ(re)) pos[re[i]]=i;
REP(i,SZ(a))
{
doo(opt,d(a[i]),pos[i%SZ(pos)]+1,rnd/SZ(a)+(i<rnd%SZ(a)),SZ(b));
}
}
void sol()
{
const int g=__gcd(SZ(A),SZ(B));
ll opt[3]={0,0,0};
REP(i,g)
{
string a,b;
for(int j=i;j<SZ(A);j+=g) a.pb(A[j]);
for(int j=i;j<SZ(B);j+=g) b.pb(B[j]);
calc(opt,a,b,T/g+(i<T%g));
}
REP(i,3) printf("%lld%c",opt[i]," \n"[i==2]);
}
int main()
{
read();
build();
sol();
return 0;
}

 6 
 於: 六月 18, 2017, 05:41:08 pm 
作者 darry140 - 最新文章 由 darry140
代碼: [選擇]
#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
//}}}
ll V;
void read()
{
scanf("%lld",&V);
}
vector<int> facs;
void build()
{
for(int i=1;i*i<=V;i++) if(V%i==0)
facs.pb(i);
int x=V;
for(int f:facs) while(f!=1 && x%f==0)
x/=f;
if(x>1) facs.pb(x);
}
void sol()
{
ll a=1,b=1,c=V;ll suf=2*(a*b+b*c+c*a);
auto upd=[&](ll i,ll j,ll k)
{
ll cs=2*(i*j+j*k+k*i);
if(tie(cs,i,j,k) < tie(suf,a,b,c))
suf=cs,a=i,b=j,c=k;
};
for(int i:facs)
{
for(auto it=lower_bound(ALL(facs),i);it!=facs.end();it++)
{
ll j=*it;
if(1LL*i*j*j>V || 0.9*i*j*j>V) break;
if(V%(i*j)==0) upd(i,j,V/i/j);
}
}
printf("%lld %lld %lld %lld\n",suf,a,b,c);
}
int main()
{
read();
build();
sol();
return 0;
}

 7 
 於: 六月 18, 2017, 05:40:23 pm 
作者 darry140 - 最新文章 由 darry140
代碼: [選擇]
#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
//}}}
const int maxn=1e6+6;
int n;ll a[maxn];
void read()
{
scanf("%d",&n);
REP1(i,1,n) scanf("%lld",&a[i]);
}
ll s[maxn];
void build()
{
REP1(i,1,n) s[i]=s[i-1]+a[i];
}
void sol()
{
vector<int> v;
ll ans=0;
for(int i=n;i>=0;i--)
{
while(SZ(v) && s[v.back()]>=s[i]) v.pop_back();
if(SZ(v)) ans+=n+1-v.back();
debug(ans);
v.pb(i);
}
cout<<ans<<endl;
}
int main()
{
read();
build();
sol();
return 0;
}

 8 
 於: 六月 18, 2017, 05:39:24 pm 
作者 darry140 - 最新文章 由 darry140
代碼: [選擇]
#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
//}}}
const int maxn=1e5+5;
int n;ll h[maxn];
ll L,U;
void read()
{
scanf("%d",&n);
scanf("%lld%lld",&L,&U);
REP1(i,1,n) scanf("%lld",&h[i]);
}
ll x[maxn],y[maxn];
struct Bit
{
ll dat[maxn];
void add(int i,ll x)
{
for(;i<=n;i+=i&-i) dat[i]+=x;
}
ll ask(int i)
{
ll ret=0;
for(;i>=1;i-=i&-i) ret+=dat[i];
return ret;
}
} bit;
ll doo(int l,int r)
{
if(l==r) return 0;
int mid=(l+r)/2;
ll ans=doo(l,mid)+doo(mid+1,r);

vector<int> req(mid-l+1);iota(ALL(req),l);
sort(ALL(req),[&](int i,int j){return y[i]<y[j];});
vector<int> pts(r-mid);iota(ALL(pts),mid+1);
sort(ALL(pts),[&](int i,int j){return y[i]<y[j];});

auto it=pts.begin();
for(auto i:req)
{
while(it!=pts.end() && y[*it]<y[i]) bit.add(x[*(it++)],1);
ll dlt=(it-pts.begin())-bit.ask(x[i]);
debug(l,mid,r,i,dlt);
ans+=dlt;
}
for(auto it2=pts.begin();it2!=it;it2++) bit.add(x[*it2],-1);
return ans;
}
ll calc(ll d)
{
REP1(i,1,n) x[i]=h[i]+d*i,y[i]=h[i]-d*i;
vector<ll> v(x+1,x+n+1);
sort(ALL(v));v.erase(unique(ALL(v)),v.end());
REP1(i,1,n) x[i]=lower_bound(ALL(v),x[i])-v.begin()+1;
return doo(1,n);
}
void sol()
{
printf("%lld\n",calc(U)-calc(L));
}
int main()
{
read();
sol();
return 0;
}


 9 
 於: 一月 24, 2017, 01:11:02 pm 
作者 daniel920712 - 最新文章 由 daniel920712
請問一下,TOI初選會有解題說明嗎?

 10 
 於: 一月 06, 2017, 02:29:09 pm 
作者 w80707 - 最新文章 由 w80707
小三角形的周長=大三角形的1/2(中位線), 溝通困難度=小三角形的周長*2
a,b,c加起來就對了...

#include<stdio.h>
int main(){
   int a,b,c;
   while(~scanf("%d%d%d",&a,&b,&c)) printf("%d\n",a+b+c);
}

頁: [1] 2 3 ... 10