Codeforces Round #210

A：简单题：

 1 #include<cstdio>
 2 using namespace std;
 3 
 4 int n,k;
 5 int main()
 6 {
 7     scanf("%d%d",&n,&k);
 8     for(int i=0; i<n; i++)
 9     {
10         for(int j=0; j<n; j++)
11         {
12             if(i==j)printf("%d ",k);
13             else printf("0 ");
14         }
15         puts("");
16     }
17     return 0;
18 }

View Code

B.简单题：

 1 #include<cstdio>
 2 using namespace std;
 3 
 4 int n,k;
 5 int main()
 6 {
 7     scanf("%d%d",&n,&k);
 8     if((n==1&&k==1)||k==n)
 9     {
10         puts("-1");
11         return 0;
12     }
13     if(k==0)
14     {
15         for(int i=1;i<n;i++)
16             printf("%d ",i+1);
17         puts("1");
18         return 0;
19     }
20     if(k==n-1)
21     {
22         for(int i=1;i<=n;i++)
23             printf("%d ",i);
24         return 0;
25     }
26     printf("%d ",k+2);
27     for(int i=2; i<=k+1; i++)
28     {
29         printf("%d ",i);
30     }
31     for(int i=k+2; i<n; i++)
32         printf("%d ",i+1);
33     printf("1");
34     return 0;
35 }

View Code

C：暴力，先从后往前搞一遍，然后从前往后检查一遍；

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define maxn 5005
 4 using namespace std;
 5 
 6 int p[maxn],ans[maxn];
 7 int cmd[maxn],l[maxn],r[maxn],num[maxn];
 8 bool vis[maxn],flag;
 9 int main()
10 {
11     int n,m;
12     scanf("%d%d",&n,&m);
13     for(int i=0;i<m;i++)scanf("%d%d%d%d",&cmd[i],&l[i],&r[i],&num[i]);
14     for(int i=1;i<=n;i++)p[i]=-10000000;
15     for(int i=m-1;i>=0;i--)
16     {
17         if(cmd[i]==1)
18         {
19             for(int j=l[i];j<=r[i];j++)
20                 p[j]-=num[i];
21         }
22         else
23         {
24             for(int j=l[i];j<=r[i];j++)
25             {
26                 if(vis[j]&&p[j]<=num[i])continue;
27                 p[j]=num[i];
28                 vis[j]=1;
29             }
30         }
31     }
32     for(int i=1;i<=n;i++)ans[i]=p[i];
33     for(int i=0;i<m;i++)
34     {
35         if(cmd[i]==1)
36         {
37             for(int j=l[i];j<=r[i];j++)
38                 p[j]+=num[i];
39         }
40         else
41         {
42             int ma=-100000000;
43             for(int j=l[i];j<=r[i];j++)
44                 ma=max(ma,p[j]);
45             if(ma!=num[i]){flag=1;break;}
46         }
47     }
48     if(flag)puts("NO");
49     else
50     {
51         puts("YES");
52         for(int i=1;i<=n;i++)
53             printf("%d ",ans[i]);
54     }
55     return 0;
56 }

View Code

D：二分+dp： |ai-aj|<=(j-i)*x

 1 #include <cstdio>
 2 #include <algorithm>
 3 #define MAXN 2005
 4 #define LL long long
 5 using namespace std;
 6 int a[MAXN] , b[MAXN] , sum , k  ,n;
 7 bool ok(int d)
 8 {
 9     for(int i = 1 ; i<= n; i++)
10         b[i] = 1;
11     for(int i = 2 ; i <= n ; i++)
12     {
13         for(int j = 1 ; j <  i ; j++)
14         {
15             if(abs(a[i] - a[j]) <= (LL)(i - j) * d)
16                 b[i] = max(b[i] , b[j] + 1);
17         }
18     }
19     sum = 0;
20     for(int i = 1 ; i <= n ; i++)sum = max(sum , b[i]);
21     return n - sum <= k;
22 }
23 int main()
24 {
25     int l = 0 , r = 2*1000000000;
26     scanf("%d%d" , &n , &k);
27     for(int i = 1 ; i <= n ; i++)scanf("%d" , &a[i]);
28     while(l <= r)
29     {
30         int Mid = ((LL)l + r) / 2;
31         if(ok(Mid))r = Mid - 1;
32         else l = Mid + 1;
33     }
34     printf("%d
" , l);
35     return 0;
36 }

View Code