#include
#include
#include
#include
#include
#include
#define exp 1e-10
using namespace std;
inline void RD(int &ret)
{
char c;
do
{
c=getchar();
}
while(c<'0'||c>'9');
ret=c-'0';
while((c=getchar())>='0'&&c<='9')
{
ret=ret*10+(c-'0');
}
}
inline void OT(int a)
{
if(a>=10)
{
OT(a/10);
}
putchar(a%10+'0');
}
struct xl
{
int x,y,id;
} s[100001];
bool cmp(xl x,xl y)//结构体排序
{
if(x.x==y.x)
{
return x.y }
return x.x }
int main()
{
int i,n,j,r;
bool v[100001];
while(scanf("%d",&n)!=EOF)
{
for(i=0; i {
RD(s[i].x);
RD(s[i].y);
s[i].id=i+1;
}
sort(s,s+n,cmp);
j=0;
r=-1;
for(i=0; i {
v[i]=false;//标记
if(s[i].x>=r)
{
r=s[i].y;
j++;
v[i]=true;
}
r=min(r,s[i].y);
}
OT(j);
for(i=0; i {
if(v[i])
{
printf("\n");
OT(s[i].id);
}
else
{
printf(" ");
OT(s[i].id);
}
}
printf("\n\n");
}
return 0;
}
J.Painting Storages

一道排列组合的题目，需要找到状态分解：

当dp[i-1]已经满足状况了：dp[i]=dp[i-1]*2；

当dp[i-1]还没满足状况，则[i-m+1,i]区间则用来满足条件，则i-m必为蓝色，所以dp[i-m-1]不能包括在内。所以需要dp[i-1]+pow(2,i-m-1)-dp[i-m-1]；

[cpp]
#include
#include
#include
#include
#include
#include
#define N 1000000007
using namespace std;
inline void RD(int &ret)
{
char c;
do
{
c=getchar();
}
while(c<'0'||c>'9');
ret=c-'0';
while((c=getchar())>='0'&&c<='9')
{
ret=ret*10+(c-'0');
}
}
inline void OT(int a)
{
if(a>=10)
{
OT(a/10);
}
putchar(a%10+'0');
}
long long dp[100001],a[100001];
void f()
{
a[0]=1;
int i;
for(i=1; i<100001; ++i)//构造2次幂表
{
a[i]=a[i-1]*2%N;
}
}
int main()
{
f();
int i,n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(dp,0,sizeof(dp));
dp[m]=1;
for(i=m+1; i<=n; ++i)
{
dp[i]=((dp[i-1]*2%N+a[i-m-1])%N-dp[i-m-1]+N)%N;//状态递推过程
}
cout< }
return 0 ;
}