CF 1136A 1136B 1136C 1136D 1136E(Round546ABCDE)题解

题目地址：https://codeforces.com/contest/1136

题解：挨个判断即可，水题。

参考代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,l[110],r[110],k;
 4 
 5 int main()
 6 {
 7     scanf("%d",&n);
 8     for(int i=1;i<=n;++i) scanf("%d%d",&l[i],&r[i]);
 9     scanf("%d",&k);
10     for(int i=1;i<=n;++i)
11     {
12         if(k>=l[i] && k<=r[i]) { cout<<n-i+1<<endl; break;}
13     }
14     
15     return 0;
16  }

View Code

B：Nastya Is Playing Computer Games

题解：找规律。ans=3*n+min(k-1,n-k);

参考代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int INF=0x3f3f3f3f;
 5 int n,k;
 6 int main()
 7 {
 8     scanf("%d%d",&n,&k);
 9     int a=min(k-1,n-k);
10     printf("%d
",3*n+a);
11     
12     
13     return 0;
14  }

View Code

C：Nastya Is Transposing Matrices

题解：如果两个位置的数可以交换，则他们的横纵坐标的和相同。我们用mp[x][0]:表示横纵坐标和为x的数量,然后mp[x][i] (i>=1):表示横纵坐标和为x的数字有哪些，

然后徐排序依次比较即可；

参考代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int inf = 0x3f3f3f3f;
 5 const int Max = 5e2 + 10;
 6 const int mod = 1e9 + 7;
 7 int map1[2*Max][Max],map2[2*Max][Max];
 8 
 9 bool cmp(int index)
10 {
11     for (int i=1; i<= map1[index][0];i++)
12     {
13         if(map1[index][i]!=map2[index][i])
14             return false;
15     }
16     return true;
17 }
18 
19 int main()
20 {
21     int n, m;
22     while (scanf("%d%d",&n,&m)!=EOF)
23     {
24         memset(map1,0,sizeof(map1));
25         memset(map2,0,sizeof(map2));
26         for (int i = 1; i <= n; i++)
27         {
28             for (int j=1;j<=m;j++)
29             {
30                 int x;
31                 scanf("%d", &x);
32                 map1[i+j][++map1[i+j][0]]=x;
33             }
34         }
35         for (int i=1;i<=n;i++)
36         {
37             for (int j=1;j<=m;j++)
38             {
39                 int x;
40                 scanf("%d", &x);
41                 map2[i+j][++map2[i+j][0]]=x;
42             }
43         }
44         bool ok=true;
45         for(int i=2;i<=n+m;i++)
46         {
47             sort(map1[i]+1,map1[i]+1+map1[i][0]);    
48             sort(map2[i]+1,map2[i]+1+map2[i][0]);
49             if(!cmp(i)){ok = false;break;}
50         }
51         if(ok) printf("YES
");
52         else printf("NO
");
53     }
54     return 0;
55 }

View Code

D：Nastya Is Buying Lunch

题解：神奇的贪心。我们先记录每个位置的贡献值，从最后一个位置的数开始，如果num[ pos[i] ]>=n-ans-i则ans++,否则,用前面一个位置的数继续更新num数组；

参考代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define PI acos(-1.0)
 4 #define mkp make_pair
 5 #define pb push_back
 6 #define fi first
 7 #define se second
 8 typedef pair<int,int> pii;
 9 typedef long long ll;
10 const int INF=0x3f3f3f3f;
11 const int maxn=3e5+10;
12 const int maxm=5e5+10;
13 int n,m,ans;
14 int pos[maxn],num[maxn];
15 vector<int> v[maxn];
16 int main()
17 {
18     scanf("%d%d",&n,&m);
19     memset(num,0,sizeof(num)); ans=0;
20     for(int i=1;i<=n;++i) scanf("%d",&pos[i]);
21     for(int i=1;i<=m;++i)
22     {
23         int x,y;
24         scanf("%d%d",&x,&y);
25         v[y].pb(x);
26     }
27     for(auto &i:v[pos[n]]) num[i]++;
28     
29     for(int i=n-1;i>0;--i)
30     {
31         if(num[pos[i]]>=n-ans-i) ans++;
32         else {for(auto &ii:v[pos[i]]) num[ii]++;}
33     }
34     printf("%d
",ans);
35     
36     return 0;
37  }

View Code

E：Nastya Hasn't Written a Legend

题解：

参考代码：

 1 #include<bits/stdc++.h>
 2 #define fi first
 3 #define se second
 4 using namespace std;
 5 typedef long long LL;
 6 typedef pair<int, int> pii;
 7 const LL lt = -1e18;
 8 const int INF = 0x3f3f3f3f;
 9 const int MXN = 1e5 + 7;
10 
11 int n, m;
12 LL ar[MXN], kr[MXN], kk[MXN];
13 LL sum[MXN<<2],flag[MXN<<2],Max[MXN<<2];
14 void build(int l,int r,int rt) 
15 {
16     flag[rt]=lt;
17     if(l==r) 
18     {
19         sum[rt]=ar[l]-kr[l-1];
20         return;
21     }
22     int mid=(l+r)>>1;
23     build(l,mid,rt<<1);build(mid+1,r,rt<<1|1);
24     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
25 }
26 void push_down(int l,int mid,int r,int rt) 
27 {
28     if(flag[rt]==lt) return;
29     flag[rt<<1]=flag[rt];
30     flag[rt<<1|1]=flag[rt];
31     sum[rt<<1]=flag[rt]*(mid-l+1);
32     sum[rt<<1|1]=flag[rt]*(r-mid);
33     flag[rt]=lt;
34 }
35 void update(int L,int R,LL v,int l,int r,int rt) 
36 {
37     if(L<=l&&r<=R) 
38     {
39         flag[rt]=v;
40         sum[rt]=v*(r-l+1);
41         return;
42     }
43     int mid=(l+r)>>1;
44     push_down(l,mid,r,rt);
45     if(L>mid) update(L,R,v,mid+1,r,rt<<1|1);
46     else if(R<=mid) update(L,R,v,l,mid,rt<<1);
47     else update(L,mid,v,l,mid,rt<<1),update(mid+1,R,v,mid+1,r,rt<<1|1);
48     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
49 }
50 LL query(int L,int R,int l,int r,int rt) 
51 {
52     if(L>R) return 0;
53     if(L<=l&&r<=R) return sum[rt];
54     int mid=(l+r)>>1;
55     push_down(l,mid,r,rt);
56     if(L>mid) return query(L,R,mid+1,r,rt<<1|1);
57     else if(R<=mid) return query(L,R,l,mid,rt<<1);
58     else return query(L,mid,l,mid,rt<<1)+query(mid+1,R,mid+1,r,rt<<1|1);
59 }
60 int main() 
61 {
62     scanf("%d", &n);
63     for(int i=1;i<=n;++i) scanf("%lld",&ar[i]);
64     for(int i=1;i<n;++i) scanf("%lld",&kr[i]);
65     for(int i=2;i<n;++i) kr[i]+=kr[i-1];
66     for(int i=1;i<n;++i) kk[i]=kk[i-1]+kr[i];
67     build(1,n,1);
68     int Q; scanf("%d", &Q);
69     char s[2]; int l, r;
70     while(Q --) 
71     {
72         scanf("%s%d%d",s,&l,&r);
73         if(s[0] == 's')
74             printf("%lld
",query(l,r,1,n,1)+kk[r-1]-(l>=2?kk[l-2]:0));
75         else 
76         {
77             int L=l,R=n,mid,ans=l;
78             ar[l]=query(l,l,1,n,1)+r;
79             while(L<=R) 
80             {
81                 mid=L+R>>1;
82                 if(ar[l]>query(mid,mid,1,n,1)) ans=mid,L=mid+1;
83                 else R=mid-1;
84             }
85             update(l,ans,ar[l],1,n,1);
86         }
87     }
88     return 0;
89 }

View Code