ABC419

A

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
#define uint unsigned long long
5
#define PII pair<int,int>
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define pf push_front
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
map<string,string> mp;
25
signed main() {
26
    mp["red"]="SSS";
27
    mp["blue"]="FFF";
28
    mp["green"]="MMM";
29
    string s;
30
    cin>>s;
31
    if(mp.count(s)) cout<<mp[s]<<endl;
32
    else cout<<"Unknown"<<endl;
33
    return 0;
34
}

B

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
#define uint unsigned long long
5
#define PII pair<int,int>
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define pf push_front
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
int n;
25
priority_queue<int,vector<int>,greater<int> > q;
26
signed main() {
27
    n=read();
28
    while(n--) {
29
        int op=read();
30
        if(op==1) {
31
            int x=read();
32
            q.push(x);
33
        } else {
34
            int x=q.top(); q.pop();
35
            cout<<x<<endl;
36
        }
37
    }
38
    return 0;
39
}

C

没做出来捏。

D

维护一个 01 串的区间反转，单点查询。

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
#define uint unsigned long long
5
#define PII pair<int,int>
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define pf push_front
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N=5e5+5;
25
int n, m;
26
string s[2];
27
namespace BIT {
28
    int c[N];
29
    int lowbit(int x) { return x&-x; }
30
    void add(int x) {
31
        for(;x<=n;x+=lowbit(x)) c[x]^=1;
32
    }
33
    int query(int x) {
34
        int y=0;
35
        for(;x;x-=lowbit(x)) y^=c[x];
36
        return y;
37
    }
38
}
39
signed main() {
40
    n=read(), m=read();
41
    cin>>s[0];
42
    cin>>s[1];
43
    s[0]=" "+s[0];
44
    s[1]=" "+s[1];
45
    while(m--) {
46
        int l=read(), r=read();
47
        BIT::add(l);
48
        BIT::add(r+1);
49
    }
50
    rep(i,1,n) {
51
        int t=BIT::query(i);
52
        cout<<s[t][i];
53
    }
54
    cout<<endl;
55
    return 0;
56
}

E

题目中的条件转化一下就是

$m \mid \sum_{i=1}^l A_i$
$\forall i \in [1,n-l]$ ， $m \mid A_{i+l}-A_i$ 。由数论知识显然。更进一步地， $A_i \equiv A_{i+l} \pmod {m}$ 。我们称同余的这个数 $j$ 为这组的特征元素。

不难发现这是充要的。考虑滑动窗口的变化。

于是每个 $A_{i},A_{i+l},A_{i+2l} ,\ldots$ 就相对独立了，可以分开考虑。

设 $f(i,j)$ 表示考虑 $[1,i]$ ，其中前 $i$ 组的特征元素的和模 $m$ 为 $j$ 时，需要的最小代价。

转移枚举当前组的特征元素 $j \in [0,m)$ ，贪心修改每个元素。然后枚举 $k$ ，用 $f(i-1,j)$ 更新 $f\left(i,\left(j+k\right) \bmod m\right)$ 即可。

复杂度 $O(nm^2)$ 。

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define ll long long
4
#define uint unsigned long long
5
#define PII pair<int,int>
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define pf push_front
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N=505;
25
int n, m, l, a[N], s[N], f[N][N];
26
signed main() {
27
    n=read(), m=read(), l=read();
28
    rep(i,1,n) {
29
        a[i]=read();
30
        s[i]=s[i-1]+a[i];
31
    }
32
    rep(i,0,n) rep(j,0,m) f[i][j]=1e9;
33
    f[0][0]=0;
34
    rep(i,1,l) rep(j,0,m-1) {
35
        int res=0;
36
        for(int k=i;k<=n;k+=l) {
37
            if(j>=a[k]) res+=j-a[k]; else res+=j-a[k]+m;
38
        }
39
        rep(k,0,m-1) f[i][(k+j)%m]=min(f[i][(k+j)%m],f[i-1][k]+res);
40
    }
41
    cout<<f[l][0]<<endl;
42
    return 0;
43
}

F

又是动态 DP？

A

B

C

D

E

F

觉得这篇文章怎么样？

分享这篇文章

评论区

搜索结果

标签

分类

搜索结果

标签

分类

A

B

C

D

E

F

觉得这篇文章怎么样？

分享这篇文章

评论区