其次组有4个数(1,ai+1也被占据了的话就尝试ai+2

如何读书医学

岁月范围: 1 Sec  内存限制: 128
MB
提交: 97  解决: 27
[提交][状态][讨论版]

题目讲述

Mr_H 出了一道信息学竞技题,就是给 n 个数排序。输入格式是这样的:
课题有几多组数据。每组数据的首个是一个整数 n,表示总共有 n
个数待排序;接下去 n 个整数,分别表示这n 个待排序的数。
譬如:3 4 2 –1 4 1 2 3 4,就意味着有两组数据。第一组有3
个数(4,2,-1),第二组有4个数(1,2,3,4)。但是现在Mr_H
做的输入数据出了一部分问题。
譬如说:2 1 9 3 2 按理说第一组数据有2 个数(1,9),第二组数据有3
个数,不过“3”前面并从未出现三个数,只现出了一个数“2”而已!
现在 Mr_H 需要对数码进行修改,改动中“一步”的意思是对文本中的某一个数+1
或-1,写个
次第,统计最少需要有些步才能将数据改得合法。

题材叙述

给n个人安排座位,先给各样人一个1~n的号码,设第i个体的号子为ai(不同人的号子可以一样),接着从第一私家先导,大家逐一入座,第i私房来
了随后尝试坐到ai,借使ai被占据了,就尝试ai+1,ai+1也被霸占了的话就尝试ai+2,……,假诺一向尝试到第n个都充分,该安排方案就不合
法。但是有m个人的编号已经确定(他们恐怕贿赂了你的上司…),你不得不安排剩下的人的号子,求有些许种合法的部署方案。由于答案恐怕很大,只需出口其
除以M后的余数即可。

题材叙述

OI大师抖儿在夺取银牌之后,顺利保送pku。这一天,抖儿问长者:“尽管我已经保送了,不过自己还要参加学考。立时就要考政治了,请问应该怎么着读书教育学,通过政治考试?”
 长者回答:“你哟,Too Young Too Simple,Sometimes
Naive!经济学这种事物,不是说想懂就能懂的,需要静心撕烤。你去前边的林英里卓越思考。”

普陀山的后院有一片哲♂学森林。由于局部奥妙重重的原因,这片山林构成了一个n*m的矩形,其中每个点就象征了一棵树。其它,由于辣鸡出题人KJDH从中捣鬼,有些树被连根拔起(也就是过眼烟云了)。抖儿每一日都要到树下撕烤,由此她想要在每一行选拔一棵树。然而他非常厌恶走回头路,因而第i行选用的树必须比第i-1行的靠右。现在抖儿想明白,总共有多少种选用的方案。

输入格式

先是行一个平头m,表示Mr_H 做的输入数据包含的平头个数。第二行包含m
个整数a[i],每个整数的绝对化值不超过10000。

输入输出格式

输入格式:

先是行一个平头T,表示数据组数

对此每组数据,第一行有多少个整数,分别表示n、m、M

若m不为0,则接下去一行有m对整数,p1、q1,p2、q2 ,…,
pm、qm,其中第i对整数pi、qi代表第pi私房的号码必须为qi

出口格式:

对此每组数据输出一行,倘若有解则输出YES,后跟一个整数表示方案数mod
M,注意,YES和数以内只有一个空格,否则输出NO

输入

首先行多少个整数n,m,p,分别代表森林的长、宽,以及没有的树的多少。

接下去p行每行五个整数,表示第ai行第bi列的树消失了。

输出格式

一个整数,表示把多少修改为法定的气象下,最少需要多少步。

输入输出样例

输入样例#1:

2
4 3 10
1 2 2 1 3 1
10 3 8882
7 9 2 9 5 10

输出样例#1:

YES 4
NO

输出

一行一个整数,表示方案数。由于答案恐怕很大,请对1000003取模。

样例输入

【样例输入1】
4
1 9 3 2

【样例输入2】
10
4 4 3 5 0 -4 -2 -1 3 5

说明

100%的数目满意:1≤T≤10,1≤n≤300,0≤m≤n,2≤M≤109,1≤pi、qi≤n
且保证pi互不相同。

先是,每个人都要有职位

这就是说意味着地点不可以有空

也就是说,对于地方i,地方在i及i前面的人要压倒i个,否则就填不满

每个i都符合条件则为官方

我们设sum[i]为能够填在1~i的人数

cnt[i]为必须填i的人口

引人注目sum能够透过cnt算出,具体方法:

sum[0]=n-m,sum[i]=sum[i-1]+cnt[i]

原因sum[i]肯定有∑cnt[1~i]接下来算上不确定的n-m个人

如此这般就足以用sum[i]<i判断无解

求方案数用dp

令f[i][j]表示前i位,放j个人

图片 1

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 ll f[301][301],cnt[301],sum[301],C[301][301],Mod,n,m;
 8 int main()
 9 {int T,i,j,p,q,flag,k;
10   cin>>T;
11   while (T--)
12     {
13       cin>>n>>m>>Mod;
14       memset(C,0,sizeof(C));
15       memset(cnt,0,sizeof(cnt));
16       memset(f,0,sizeof(f));
17       C[0][0]=1;
18       for (i=1;i<=300;i++)
19     {C[i][0]=1;
20       for (j=1;j<=i;j++)
21         C[i][j]=C[i-1][j]+C[i-1][j-1],C[i][j]%=Mod;
22     }
23       for (i=1;i<=m;i++)
24     {
25       scanf("%d%d",&p,&q);
26       cnt[q]++;
27     }
28       sum[0]=n-m;flag=1;
29       for (i=1;i<=n;i++)
30     {
31       sum[i]=sum[i-1]+cnt[i];
32       if (sum[i]<i) 
33         {
34           cout<<"NO\n";
35           flag=0;break;
36         }
37     }
38       if (flag) 
39     {
40       f[0][0]=1;
41       for (i=1;i<=n;i++)
42         {
43           for (j=i;j<=sum[i];j++)
44         {
45           for (k=cnt[i];k<=j-i+1;k++)
46             {
47               f[i][j]+=f[i-1][j-k]*C[sum[i-1]-(j-k)][k-cnt[i]]%Mod;
48               f[i][j]%=Mod;
49             }
50         }
51         }
52       cout<<"YES "<<f[n][n]<<endl;
53     }
54     }
55 }

 

样例输入

3 5 2 2 3 3 4

样例输出

【样例输出1】
2

【样例输出2】
3

样例输出

5

提示

【数据范围】
对于 20%的数据,m<=10, |a[i]|<=5;
对于60%的数据,m<=5000, |a[i]|<=10000
对于100%的数据,m<=100000, |a[i]|<=10000


来源  by
YZ

 

【题解】

dp(i)=min{dp(j)+|num(j+1)-(i-j-1)|}

num(j+1)-(i-j-1)>=0
,即i<num(j+1)+j+1时 dp(i)=min{dp(j)+num(j+1)+j+1}-i
num(j+1)-(i-j-1)<0,即i>num(j+1)+j+1时
dp(i)=min{dp(j)-num(j+1)-j-1}-i
俺们不难用一颗权值线段树去维护,线段树的下标表示num(j+1)+j+1,值
为dp(j)-num(j+1)-j-1 
/ dp(j)+num(j+1)+j+1的蝇头值。

询问dp(j)+num(j+1)+j+1线段树的i….max和

dp(j)-num(j+1)-j-1线段树的1…i-1即可

对拍无误

 

图片 2图片 3

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #define max(a, b) ((a) > (b) ? (a) : (b))
 6 #define min(a, b) ((a) < (b) ? (a) : (b))
 7 
 8 inline void read(int &x)
 9 {
10     x = 0;char ch = getchar(), c = ch;
11     while(ch < '0' || ch > '9')c = ch, ch = getchar();
12     while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar();
13     if(c == '-')x = -x; 
14 }
15 
16 const int MAXM = 200000 + 10;
17 const int MAXNUM = 1000000;
18 const int PIAN = 11000;
19 const int INF = 0x3f3f3f3f;
20 
21 int m,dp[MAXM],num[MAXM];
22 
23 int mi[2][MAXNUM + 10], sum;
24 /*
25 f(i)=min{f(j)+|A(j+1)-(i-j-1)|}
26 0: num(j+1)-(i-j-1)>0 -> i<num(j+1)+j+1  f(i)=min{f(j) + num(j+1) - (-j-1)} - i
27 1: num(j+1)-(i-j-1)<=0 -> i>num(j+1)+j+1 f(i)=min{f(j) + (-j-1) - num(j+1)} + i
28 */
29 
30 void modify(int a, int p, int k, int o = 1, int l = 1, int r = sum + PIAN)
31 {
32     if(l == r && l == p)
33     {
34         mi[a][o] = min(k, mi[a][o]);
35         return;
36     }
37     int mid = (l + r) >> 1;
38     if(mid >= p)modify(a, p, k, o << 1, l, mid);
39     else modify(a, p, k, o << 1 | 1, mid + 1, r);
40     mi[a][o] = min(mi[a][o], min(mi[a][o << 1], mi[a][o << 1 | 1]));
41 }
42 
43 int ask(int a, int ll, int rr, int o = 1, int l = 1, int r = sum + PIAN)
44 {
45     if(ll <= l && rr >= r) return mi[a][o];
46     int mid = (l + r) >> 1;
47     int ans = INF;
48     if(mid >= ll)ans = min(ans, ask(a, ll, rr, o << 1, l, mid));
49     if(mid < rr)ans = min(ans, ask(a, ll, rr, o << 1 | 1, mid + 1, r));
50     return ans;
51 }
52 
53 int main()
54 {
55     read(m);
56     for(register int i = 1;i <= m;++ i)
57         read(num[i]), sum = max(sum, num[i] + i + 1 + PIAN);
58     memset(dp, 0x3f, sizeof(dp));
59     memset(mi, 0x3f, sizeof(mi));
60     dp[0] = 0;
61     modify(0,num[1] + 1 + PIAN, num[1] + 1);
62     modify(1,num[1] + 1 + PIAN, -num[1] - 1); 
63     for(register int i = 1;i <= m;++ i)
64     {
65         int k1 = ask(0, min(sum, i) + PIAN, sum + PIAN) - i;
66         int k2 = ask(1, 1, max(1, i - 1) + PIAN) + i;
67         if(k2 <= i - INF)k2 = INF;
68         dp[i] = min(dp[i], min(k1, k2));
69         modify(0, num[i + 1] + i + 1 + PIAN, dp[i] + num[i + 1] + i + 1);
70         modify(1, num[i + 1] + i + 1 + PIAN, dp[i] - num[i + 1] - i - 1);
71     }
72     printf("%d", dp[m]);
73     return 0;
74 }

my

 

图片 4图片 5

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<queue>
 7 using namespace std;
 8 const int inf=0x3f3f3f3f;
 9 template <typename T>
10 inline void _read(T& x){
11     char t=getchar();bool sign=true;
12     while(t<'0'||t>'9')
13     {if(t=='-')sign=false;t=getchar();}
14     for(x=0;t>='0'&&t<='9';t=getchar())x=x*10+t-'0';
15     if(!sign)x=-x;
16 }
17 int n;
18 int a[200005];
19 int f[200005];
20 int mark[200005];
21 vector<int> v[200005];
22 struct node{
23     int x,y;
24     node(){}
25     node(int g,int h){x=g;y=h;}
26     bool operator < (const node p)const {
27         return y>p.y;
28     }
29 };
30 priority_queue<node>q1;
31 priority_queue<node>q2;
32 void dajia(){
33     int i,j,k;
34     for(i=1;i<=n;i++){
35         f[i]=inf;
36         for(k=i-1;k>=0;k--){
37             f[i]=min(f[i],f[k]+abs(a[k+1]-(i-k-1)));
38         }
39     }
40 }
41 void daqunjia(){
42     int i,j,k,temp;
43     q1.push(node(0,a[1]+1));
44     for(i=1;i<=n;i++){
45         temp=-1;
46         for(j=0;j<v[i].size();j++){
47             mark[v[i][j]]=2;
48             if(v[i][j]<i)q2.push(node(v[i][j],f[v[i][j]]-a[v[i][j]+1]-v[i][j]-1));
49         }
50         while(q1.size()&&mark[q1.top().x]==2){
51             q1.pop();
52         }
53         if(q1.size()){
54             temp=q1.top().y-i;
55         }
56         if(q2.size()){
57             if(temp==-1)temp=q2.top().y+i;
58             else temp=min(temp,q2.top().y+i);
59         }
60         f[i]=temp;
61         if(mark[i]==2){
62             q2.push(node(i,f[i]-a[i+1]-i-1));
63         }
64         else q1.push(node(i,f[i]+a[i+1]+i+1));
65     } 
66 }
67 int main(){
68     freopen("data.txt", "r", stdin); 
69     int i,j,k,temp;
70     cin>>n;
71     for(i=1;i<=n;i++){
72         _read(a[i]);
73         if(a[i]+i<=1)v[1].push_back(i-1);
74         v[a[i]+i].push_back(i-1);
75     }
76     if(n<=5000)dajia();
77     else daqunjia();
78     cout<<f[n];
79 } 

std

图片 6图片 7

 1 #include <bits/stdc++.h>
 2 
 3 const int MAXN = 100000;
 4 const int MAXNUM = 10000;
 5 
 6 int main()
 7 {
 8     srand(time(NULL));
 9     int n = rand() % MAXN + 1;
10     printf("%d\n", n);
11     for(register int i = 1;i <= n;++ i)
12     {
13         int b = rand()%2;
14         if(b) printf("%d ",-rand()%MAXNUM+1);
15         else printf("%d ", rand()%MAXNUM+1);
16     }
17     return 0;
18 }

rand

 

 

 

 

提示

 

【样例表达】

方案一:选(1,1)(2,2)(3,3)

方案二:选(1,1)(2,2)(3,5)

方案三:选(1,1)(2,4)(3,5)

方案四:选(1,2)(2,4)(3,5)

方案五:选(1,3)(2,4)(3,5)

 

题解,可以将其看做三角形的一个近似的,走法问题,就是半三角形走法,然后就是发现方案数是C(n,m),那一个是足以推出去,

然后就是dp,当前节点的方案数总,是它左上部分通过不合法点到达其的方案数之和,相减即为走到该点方案数。

这么能够注脚,到该点的方案数是拥有,因为任何经过左上的dp[i]方案中,是代表到达dp[i]的官方方案数,由此通过数学归结法得证,

以此臆度是无可非议的,为了便利,将n+1,m+1这棵树拔掉,然后这多少个点的方案数,就为结果了。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<iostream>
 6 #define mod 1000003
 7 #define ll long long
 8 #define Q 2007 
 9 using namespace std;
10 
11 int n,m,q;
12 ll p[mod+7],inv[mod+7],dp[Q];
13 struct Node
14 {
15     int x,y;
16 }a[Q];
17 
18 bool cmp(Node x,Node y)
19 {
20     return x.x<y.x;
21 }
22 ll ksm(ll a,ll b)
23 {
24     ll ans=1;
25     while (b)
26     {
27         if (b&1) ans=a*ans%mod;
28         b/=2;
29         a=a*a%mod;
30     }
31     return ans;
32 }
33 ll Lucas_C(int n,int m)
34 {
35     if (n<m) return 0;
36     if (m==0) return 1;
37     if (n==m) return 1;
38     if (n<mod) return p[n]*inv[m]%mod*inv[n-m]%mod;
39     else return Lucas_C(n%mod,m%mod)*Lucas_C(n/mod,m/mod)%mod;
40 }
41 int main()
42 {
43     p[1]=1;
44     for (int i=2;i<=mod;i++)
45         p[i]=(p[i-1]*i)%mod;
46     for (int i=1;i<=mod;i++)
47         inv[i]=ksm(p[i],mod-2);
48     scanf("%d%d%d",&n,&m,&q);
49     
50     for (int i=1;i<=q;i++)
51         scanf("%d%d",&a[i].x,&a[i].y);
52     q++,a[q].x=n+1,a[q].y=m+1;
53     sort(a+1,a+q+1,cmp);
54     for (int i=1;i<=q;i++)
55     {
56         dp[i]=Lucas_C(a[i].y-1,a[i].x-1);
57         for (int j=1;j<i;j++)
58             if (a[i].x>a[j].x&&a[i].y>a[j].y)
59                 dp[i]=(dp[i]-dp[j]*Lucas_C(a[i].y-a[j].y-1,a[i].x-a[j].x-1)%mod+mod)%mod;            
60     }
61     printf("%lld",dp[q]);
62 }

 

相关文章