T1 【NOIP2018模拟】礼物
题解：
期望递推
\(code\):
#include
#include
#include
#include
#define ll long long
#define ld double
#define eps 1e-7
using namespace std;
char buf[1<<20],*p1,*p2;
inline char gc()
{
return getchar();
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++;
}
template
inline void read(T &x)
{
char tt;
bool flag=0;
while(!isdigit(tt=gc())&&tt!='-');
tt=='-'?(flag=1,x=0):x=tt^'0';
while(isdigit(tt=gc())) x=(x<<1)+(x<<3)+(tt^'0');
}
const int maxn=21;
int n,w[maxn],tot;
ll ans;
ld f[1<>i&1)
{
t1+=p[i+1];
t2+=p[i+1]*f[s^(1<
T2 【NOIP2018模拟】通讯
题解：
\(tarjan\)缩点贪心找所有点入边最短;
\(code:\)
找不到了qwq
T3 【NOIP2018模拟】奇袭
题解：
线段树维护,考虑每次移动的影响
\(code:\)
#include
#include
#include
#include
#define ll long long
using namespace std;
char buf[1<<20],*p1,*p2;
inline char gc()
{
// return getchar();
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++;
}
template
inline void read(T &x)
{
char tt;
while(!isdigit(tt=gc()));x=tt^'0';
while(isdigit(tt=gc())) x=(x<<1)+(x<<3)+(tt^'0');
}
ll n,mi[2400001],sum[2400001],lazy[2400001],M=1;
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r>>1)
void modify(int p,int l,int r,int x,int y,ll d)
{
if(l==x&&r==y)
{
mi[p]+=d;
lazy[p]+=d;
return;
}
if(x<=mid) modify(ls,l,mid,x,min(y,mid),d);
if( y>mid) modify(rs,mid+1,r,max(x,mid+1),y,d);
if(mi[ls]==mi[rs])
mi[p]=mi[ls]+lazy[p],sum[p]=sum[ls]+sum[rs];
else
{
int t=mi[ls]mid) query(rs,mid+1,r,max(x,mid+1),y);
}
void maketree(int p,int l,int r)
{
if(l==r)
{
mi[p]=0;
sum[p]=1;
return;
}
maketree(ls,l,mid);
maketree(rs,mid+1,r);
mi[p]=0;
sum[p]=r-l+1;
}
int la,lb,posa[600001],posb[600001],a[600001],b[600001],s[600001];
int main()
{
read(n);
for(int i=1,x;i<=n;i++)
read(x),read(s[x]);
posa[0]=n+1;posb[0]=n+1;
maketree(1,1,n);
for(int i=n;i;i--)
{
while(la&&a[la]<=s[i])
{
modify(1,1,n,posa[la],posa[la-1]-1,s[i]-a[la]);
--la;
}
while(lb&&b[lb]>=s[i])
{
modify(1,1,n,posb[lb],posb[lb-1]-1,b[lb]-s[i]);
--lb;
}
a[++la]=s[i];posa[la]=i;
b[++lb]=s[i];posb[lb]=i;
dep=0;
query(1,1,n,i,n);
modify(1,1,n,i,n,-1);
}
printf("%lld",ans);
}
T4 【SNOI2017 DAY1】炸弹
题解：
线段树优化建图,\(tarjan\)缩点,然而可以\(O(N)\)扫过去记录左右最大;
\(code:\)
#include
#include
#include
#include
#define ll long long
using namespace std;
const int mod=1e9+7;
char buf[1<<20],*p1,*p2;
inline char gc()
{
// return getchar();
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++;
}
template
inline void read(T &x)
{
char tt;
bool flag=0;
while(!isdigit(tt=gc())&&tt!='-');
tt=='-'?(flag=1,x=0):(x=tt^'0');
while(isdigit(tt=gc())) x=(x<<1)+(x<<3)+(tt^'0');
if(flag) x=-x;
}
ll n,x[500005],R[500005],l[500005],r[500005],ans;
main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld%lld",&x[i],&R[i]),l[i]=r[i]=i;
for(int i=1;i<=n;i++)
while(l[i]>1&&x[i]-x[l[i]-1]<=R[i])
l[i]=l[l[i]-1],R[i]=max(R[i],R[l[i]]-(x[i]-x[l[i]]));
for(int i=n;i>=1;i--)
while(r[i]
T5 最后战役
题解：
神仙题,期望递推
\(code:\)
待补
T6 分成互质组
题解：
状压,\(O(N^2)\)枚举两两关系,\(g[S]\)数组维护其中元素的合法性,状态转移:\(F[S]=min\{F[S']+1\}(g[S \bigoplus S']==1)\)
\(code:\)
#include
#include
#include
using namespace std;
int n;
int a[20],f[1<<20],cnt[1<<20];
bool g[1<<20],w[20][20];
int gcd(int a,int b)
{
if(!b) return a;
return gcd(b,a%b);
}
int lowbit(int x)
{
return x&-x;
}
int main()
{
scanf("%d",&n);
memset(f,30,sizeof(f));
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),cnt[1<>(j-1)&1) if(!w[cnt[lowbit(i)]][j])
{flag=1;break;}
if(!flag) g[i]=1;
}
f[0]=0;
// for(int i=1;i<=10;i++)printf("%d ",g[i]);
for(int i=1;i<1<