比赛链接 。

第一题

正常

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import java.io.*;

import java.util.*;
public class Main {
    static int zu;
    public static void main(String[] args) {
        zu=in.nextInt();
        while(zu-->0) solve();
        out.flush();
    }
    static void solve(){
        String s;
        s=in.next();
        Map<Character,Integer> mp=new HashMap<>();
        for(int i=0;i<4;i++){
            char c=s.charAt(i);
            mp.put(c,mp.getOrDefault(c,0)+1);
        }
        if(mp.size()==2){
            boolean st[]=new boolean[10];
            for(char key:mp.keySet()){
                st[mp.get(key)]=true;
            }
            if(st[1]&&st[3]) out.println("Yes");
            else out.println("No");
        }else{
            out.println("No");
        }
    }

    static FastReader in = new FastReader();
    static PrintWriter out=new PrintWriter(System.out);
    static class FastReader{
        static BufferedReader br;
        static StringTokenizer st;
        FastReader(){
            br=new BufferedReader(new InputStreamReader(System.in));
        }
        String next(){
            String str="";
            while(st==null||!st.hasMoreElements()){
                try {
                    str=br.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                st=new StringTokenizer(str);
            }
            return st.nextToken();
        }
        int nextInt(){
            return Integer.parseInt(next());
        }
        double nextDouble(){
            return Double.parseDouble(next());
        }
        long nextLong(){
            return Long.parseLong(next());
        }
    }
}

普通的题，无误

第二题

正常

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import java.io.*;

import java.util.*;

public class Main{
    static int zu;
    public static void main(String[] args) {
        zu=1;
        while(zu-->0) solve();
        out.flush();
    }
    static void solve(){
		int n,q;
        n=in.nextInt();
        q=in.nextInt();
        int res=1;
        for(int i=1;i<=q;i++){
            String s=in.next();
            res=1;
            for(int j=0;j<s.length();j++){
                if(s.charAt(j)=='R'){
                  	res=res*2;  
                }else{
                    res=res*2-1;
                }
            }
            out.println(res);
        }
    }

    static FastReader in = new FastReader();
    static PrintWriter out=new PrintWriter(System.out);
    static class FastReader{
        static BufferedReader br;
        static StringTokenizer st;
        FastReader(){
            br=new BufferedReader(new InputStreamReader(System.in));
        }
        String next(){
            String str="";
            while(st==null||!st.hasMoreElements()){
                try {
                    str=br.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                st=new StringTokenizer(str);
            }
            return st.nextToken();
        }
        int nextInt(){
            return Integer.parseInt(next());
        }
        double nextDouble(){
            return Double.parseDouble(next());
        }
        long nextLong(){
            return Long.parseLong(next());
        }
    }
}

简单思维，无误。

第三题

正常

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import java.io.*;

import java.util.*;

public class Main{
    static int zu;
    public static void main(String[] args) {
        zu=1;
        while(zu-->0) solve();
        out.flush();
    }
    static boolean check(int a[],int k,int mid){
        int start=a[1];
        int g=1;
        for(int i=2;i<=n;i++){
            if(a[i]-start>mid){
                g++;
                start=a[i];
                if(g>k) return false;
            }
        }
        return true;
    }
    static int n;
    static void solve(){
        n=in.nextInt();
        int k=in.nextInt();
        int a[]=new int[n+10];
        for(int i=1;i<=n;i++) a[i]=in.nextInt();
        Arrays.sort(a,1,n+1);
        int l=0,r= (int) (1e9+7);
        while(l<r){
            int mid=l+r>>1;
            if(check(a,k,mid)){
                r=mid;
            }else{
                l=mid+1;
            }
        }
        out.println(l);
    }

    static FastReader in = new FastReader();
    static PrintWriter out=new PrintWriter(System.out);
    static class FastReader{
        static BufferedReader br;
        static StringTokenizer st;
        FastReader(){
            br=new BufferedReader(new InputStreamReader(System.in));
        }
        String next(){
            String str="";
            while(st==null||!st.hasMoreElements()){
                try {
                    str=br.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                st=new StringTokenizer(str);
            }
            return st.nextToken();
        }
        int nextInt(){
            return Integer.parseInt(next());
        }
        double nextDouble(){
            return Double.parseDouble(next());
        }
        long nextLong(){
            return Long.parseLong(next());
        }
    }
}

二分一下即可

第四题

正常

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import java.io.*;

import java.util.*;

public class Main{
    static int zu;
    public static void main(String[] args) {
        zu=1;
        while(zu-->0) solve();
        out.flush();
    }
    static int n,q;
    static int N=200010;
    static int v[]=new int[N],w[]=new int[N];
    static int a[]=new int[N];
    static long calc(int m){
        long dp[]=new long[m+10];
        for(int i=1;i<=q;i++){
            for(int j=v[i];j<=m;j++){
                dp[j]=Math.max(dp[j],dp[j-v[i]]+w[i]);
            }
        }
        return dp[m];
    }
    static void solve(){
        n=in.nextInt();
        int m=in.nextInt();
        q=in.nextInt();
        for(int i=1;i<=q;i++) a[i]=in.nextInt();
        Arrays.sort(a,1,q+1);
        for(int i=1;i<=m;i++){
            int t=in.nextInt();
            v[i]=1<<t;
            w[i]=in.nextInt();
        }
        a[0]=0;
        long res=0;
        a[q+1]=n+1;
        for(int i=1;i<=q+1;i++){
            res=res+calc(a[i]-a[i-1]-1);
        }
        out.println(res);
    }

    static FastReader in = new FastReader();
    static PrintWriter out=new PrintWriter(System.out);
    static class FastReader{
        static BufferedReader br;
        static StringTokenizer st;
        FastReader(){
            br=new BufferedReader(new InputStreamReader(System.in));
        }
        String next(){
            String str="";
            while(st==null||!st.hasMoreElements()){
                try {
                    str=br.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                st=new StringTokenizer(str);
            }
            return st.nextToken();
        }
        int nextInt(){
            return Integer.parseInt(next());
        }
        double nextDouble(){
            return Double.parseDouble(next());
        }
        long nextLong(){
            return Long.parseLong(next());
        }
    }
}

拆开来做完全背包，但是第一行输入是nmq，后面输入顺序是qm，建议改下，有点搞人了。

第五题

正常

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
import java.io.*;

import java.util.*;

public class Main{
    static int zu;
    public static void main(String[] args) {
        zu=1;
        while(zu-->0) solve();
        out.flush();
    }
    static void solve(){
        int n=in.nextInt();
        String s=in.next();
        String t=in.next();
        char st[]=new char[3*n+10];
        int next[]=new int[3*n+10];
        for(int i=0;i<n;i++){
            char c=s.charAt(i);
            if(c<='z'&&c>='a') c=Character.toUpperCase(c);
            else if(c<='Z'&&c>='A')c=Character.toLowerCase(c);
            st[i]=c;
        }
        st[n]='#';
        for(int i=n+1,j=0;i<=2*n;j++,i++){
            st[i]=t.charAt(j);
        }
        for(int i=2*n+1,j=0;i<=3*n;i++,j++){
            st[i]=t.charAt(j);
        }
        int ans=0x3f3f3f3f;
        //bca abc
        //bca#abcabc
        for(int i=1;i<=3*n;i++){
            int len=next[i-1];
            while (len>0&&st[i]!=st[len]) len=next[len-1];
            if(st[i]==st[len]) len++;
            next[i]=len;
            if(next[i]==n){
                ans=Math.min(ans,i-2*n);
                ans=Math.min(ans,3*n-i);
            }
        }
        if(ans==0x3f3f3f3f){
            out.println("No");
        }else{
            out.println("Yes");
            out.println(ans);
        }
    }

    static FastReader in = new FastReader();
    static PrintWriter out=new PrintWriter(System.out);
    static class FastReader{
        static BufferedReader br;
        static StringTokenizer st;
        FastReader(){
            br=new BufferedReader(new InputStreamReader(System.in));
        }
        String next(){
            String str="";
            while(st==null||!st.hasMoreElements()){
                try {
                    str=br.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                st=new StringTokenizer(str);
            }
            return st.nextToken();
        }
        int nextInt(){
            return Integer.parseInt(next());
        }
        double nextDouble(){
            return Double.parseDouble(next());
        }
        long nextLong(){
            return Long.parseLong(next());
        }
    }
}

kmp一下就行

第六题

正常

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include<bits/stdc++.h>

using namespace std;
const int maxn = 2e5 + 5;
int n, m;
pair<int, int> p1[maxn];


struct tx {
    int a, b, i, ans;

} p2[maxn];
vector<tx> p4, p3;

bool cmp(pair<int, int> a, pair<int, int> b) {
//    if (a.second == b.second) {
        return a.first > b.first;
//    }
//    return a.second > b.second;
}

bool cmp2(pair<int, int> a, pair<int, int> b) {
    if (a.second == b.second) {
        return a.first > b.first;
    }
    return a.second < b.second;
}

bool cmp3(tx tt, tx yy) {
    if (yy.b == tt.b) {
        return yy.i > tt.i;
    }
    return yy.b > tt.b;
}

bool cmp4(tx tt, tx yy) {
    if (yy.b == tt.b) {
        return yy.i > tt.i;
    }
    return yy.b < tt.b;
}

template<class Info, class Tag>
struct Segtree {
#define lson k << 1, l, mid
#define rson k << 1 | 1, mid + 1, r
    int n;
    vector<Info> info;
    vector<Tag> tag;

    Segtree(int _n) : n(_n), info((_n + 5) << 2), tag((_n + 5) << 2) {};


    void pushdown(int k, int l, int r) {
        int mid = l + r >> 1, lt = k << 1, rt = k << 1 | 1;
        info[lt].down(tag[k], mid - l + 1);
        info[rt].down(tag[k], r - mid);
        tag[lt].down(tag[k]);
        tag[rt].down(tag[k]);
        tag[k] = Tag();//初始化tag
    }

    void pushup(int k) {
        info[k] = merge(info[k << 1], info[k << 1 | 1]);
    }

    void sigupd(int k, int l, int r, int x, int y, Info &z) {
        if (l > y || r < x) return;
        if (l == r) return void(info[k] = z);
        if (tag[k].change()) pushdown(k, l, r);
        int mid = l + r >> 1;
        sigupd(lson, x, y, z), sigupd(rson, x, y, z);
        pushup(k);
    }

    void upd(int k, int l, int r, int x, int y, Tag &z) {
        if (l > y || r < x) return;
        if (l >= x && r <= y) {
            info[k].down(z, r - l + 1);
            tag[k].down(z);
            return;
        }
        if (tag[k].change()) pushdown(k, l, r);
        int mid = l + r >> 1;
        upd(lson, x, y, z), upd(rson, x, y, z);
        pushup(k);
    }

    Info qry(int k, int l, int r, int x, int y) {
        if (l > y || r < x) return Info();
        if (l >= x && r <= y) return info[k];
        if (tag[k].change()) pushdown(k, l, r);
        int mid = l + r >> 1;
        return merge(qry(lson, x, y), qry(rson, x, y));
    }

    void sigupd(int x, int y, Info &z) {
        sigupd(1, 1, n, x, y, z);
    }

    void upd(int l, int r, Tag &z) {
        upd(1, 1, n, l, r, z);
    }

    Info qry(int l, int r) {
        return qry(1, 1, n, l, r);
    }
};
struct Tag {
    int val;

    bool change() { return val != 0; }

    void down(const Tag &t) {
        //标记下放
        val += t.val;
    }
};
struct Info {
    int sum;
    void down(const Tag &t, int len) {
        //标记下放
        sum += t.val * len;
    }
    friend Info merge(const Info &a, const Info &b) {
        Info res;
        res.sum = a.sum + b.sum;
        return res;
    }
};
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> p1[i].first >> p1[i].second;
    }
    for (int i = 1; i <= m; i++) {
        cin >> p2[i].a >> p2[i].b;
        p2[i].i = i;
        p2[i].ans = 0;
        if (p2[i].a > p2[i].b) {
            p4.emplace_back(p2[i]);
        } else {
            p3.emplace_back(p2[i]);
        }
    }
    sort(p1 + 1, p1 + 1 + n, cmp2);
    sort(p3.begin(), p3.end(), cmp3);
    sort(p4.begin(), p4.end(), cmp4);
    Tag  t;
    t.val = 1;
    Segtree<Info, Tag> segtree1(maxn);
    for (int i = 0, j = 1; i < p3.size(); i++) {
        while (j <= n && p3[i].b - 1 >= p1[j].second) {
            segtree1.upd(p1[j].first, p1[j].second, t);
            j++;
        }
        p3[i].ans = segtree1.qry(p3[i].a, p3[i].a).sum;
        p2[p3[i].i].ans = p3[i].ans;
    }
    Segtree<Info, Tag> segtree2(maxn);
    sort(p1 + 1, p1 + 1 + n, cmp);
    for(int i = 0 ,j = 1; i < p4.size() ; i++){
        while (j <= n && p4[i].b + 1 <= p1[j].first) {
            segtree2.upd(p1[j].first, p1[j].second, t);
            j++;
        }
        p4[i].ans = segtree2.qry(p4[i].a, p4[i].a).sum;
        p2[p4[i].i].ans = p4[i].ans;
    }
    for(int i = 1 ; i <= m ; i ++){
        cout<<p2[i].ans<<"\n";
    }

}

离线处理+扫描线