解题报告

根据题意首先要知道-1的情况即 s==t 然后s和t都在起点和终点的时候那么直接使用超能力不需要费能力即可完成，然后就是t和s他们的绝对值相差一的情况下或者一个在终点一个在起点的情况下则为1即可，剩下均为2

Code :
#include <iostream>
#include <cmath>
#include<cstdio>
using namespace std;
int main() {
    int n, s, t;
    while (cin >> n >> s >> t) {
        if (s == t && t == 1) {
            printf("0");
            printf("\n");
        } else if (s == t) {
            printf("-1");
            printf("\n");
        } else if ((t == 1 && s == n || (t == n && s == 1))) {
            printf("0");
            printf("\n");

        } else {
            if (s == t + 1 || s == t - 1 || s == 1 || s == n || t == n || t == 1) {
                printf("1");
                printf("\n");
            } else {
                printf("2");
                printf("\n");
            }
        }
    }
    return 0;
}

B:剪绳子

看到题目，我们不知道两个值即剪掉的长度还有每一条可以剪几根这样的长度，在不考虑时间复杂度的情况下，我们需要用最小值遍历到最大值来进行裁剪计算绳子最长长度，很显然1e5的数据情况下，O(n^2)的做法无法通过，那我们就需要去思考怎么样优化，通过思考得到这显然是一道二分答案的题目，二分绳子的长度，遍历一个数组计算可以剪多少根，判断是否能满足m根的需求，因为是保留两位小数，则这里退出二分的条件就并不是l<r，应改为r-l<0.001即可

Code:
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int n,m;
bool check(double res) {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        cnt += (int) (a[i] / res);
    }
    return cnt >= m;
}
int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        double l = 0, r = 1e9;
        double res;
        while (r - l > 0.001) {
            res = (l + r) / 2;
            if (check(res)) {
                l = res;
            } else {
                r = res;
            }
        }
        printf("%.2f\n", r);
    }
}

C:混合背包

dp，由01背包，多重背包，完全背包组成的混合题。模板题，了解过3种背包模板题就能写。由于正式比赛出的dp题都会很难，所以有远大志向的可以深入dp，不明白的地方问会解答。

#include <iostream>
using namespace std;

const int N = 1e3 + 3;
int n, m;
int dp[N];
struct M {
    int w, c, p;
}; M a[N];

int main() {
    cin >> m >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].w >> a[i].c >> a[i].p;

    for (int i = 1; i <= n; i++) {
        if (!a[i].p) {//完全背包
            for (int w = a[i].w; w <= m; w++)
                dp[w] = max(dp[w], dp[w - a[i].w] + a[i].c);
        } else {//01背包和多重背包性质一样，所以统一讨论
            for (int k = 1; k <= a[i].p; k++)
                for (int w = m; w >= a[i].w; w--)
                    dp[w] = max(dp[w], dp[w - a[i].w] + a[i].c);
        }
    }

    cout << dp[m];
    return 0;
}

D:最右边

用第一个字符去遍历一整个字符串即可，相同更新位置，水题

#include <iostream>
using namespace std;

int main() {
    int t; cin >> t;
    while (t--) {
        int ans;
        string s;
        cin >> s;
        for (int i = 0; i < s.size(); i++) if (s[i] == s[0]) ans = i + 1;
        cout << ans << '\n';
    }
    return 0;
}

E:订单流程

模拟，但是要注意，如果订单状态是不符合下一步状态的话则无法完成

Code:(无stl写法，想了解stl写法联系我)

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<list>
#include<math.h>
#include<cstring>
#include<vector>
#include<stdlib.h>
using namespace std;
struct Set
{
    string name;
    int steal;
    int send;
    int finish;
}ch[1005];
int main() {
    int n;
    while (cin >> n) {
        int num = 0;
        for (int l = 0; l < n; l++) {
            string s;
            cin >> s;
            string temp;
            if (s == "add") {
                cin >> ch[num].name;
                ch[num].steal = 0;
                ch[num].send = 0;
                ch[num].finish = 0;
                num++;
            } else if (s == "steal") {
                cin >> temp;
                for (int i = 0; i < num; i++) {
                    if (ch[i].name == temp) {
                        if (ch[i].send == 0 && ch[i].finish == 0) {
                            ch[i].steal++;
                        } else {
                            ch[i].steal = -99999;
                        }
                    }
                }
            } else if (s == "send") {
                cin >> temp;
                for (int i = 0; i < num; i++) {
                    if (ch[i].name == temp) {
                        if (ch[i].steal == 1 && ch[i].finish == 0) {
                            ch[i].send++;
                        } else {
                            ch[i].send = -99999;
                        }
                    }
                }
            } else if (s == "finish") {
                cin >> temp;
                for (int i = 0; i < num; i++) {
                    if (temp == ch[i].name) {
                        if (ch[i].send == 1 && ch[i].steal == 1) {
                            ch[i].finish++;
                        } else {
                            ch[i].finish = -9999999;
                        }
                    }
                }
            }
        }
        int sum = 0;
        for (int i = 0; i < num; i++) {
            if (ch[i].steal == 1 && ch[i].send == 1 && ch[i].finish == 1) {
                sum++;
            }
        }
        cout << sum << endl;
    }
}

F:任务

跟b一样的思路，但是要注意的是要用贪心思想去判断先完成什么，很显然这题先完成钱多的，即需要对数组从大到小排序，然后再利用二分去判断这个k能否完成即可

ps:通过tzoj并不是完整数据，如想测试完整数据就去https://codeforces.com/contest/1760/problem/F

Code:

int arr[200005];
bool cmp(int a,int b){
    return a>b;
}
int n, c, d;
bool check(int x){
    int res=0;
    int j=1;
    for(int i=1;i<=d;i++){
        res+=arr[j];
        j++;
        if(i%(x+1)==0){
            j=1;
        }
    }
    return res>=c;
}
void solve() {
    memset(arr,0,sizeof(arr));
    cin >> n >> c >> d;
    for (int i = 1; i <= n; i++)cin >> arr[i];
    sort(arr + 1, arr + n + 1,cmp);
    if(check(99999999999999999)) {
        cout << "Infinity\n";
        return;
    }
    if(!check(0)){
        cout << "Impossible\n";
        return;
    }
    int l = 0, r = 999999999;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    cout << l << '\n';
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int tt = 1;
    cin >> tt;
    while (tt--) {
        solve();
    }

    return 0;
}

G:简单题

(防ak，有兴趣的同学可以看一下题解)

看见题目区间操作并且是区间在线更新，单点查询可以使用树状数组或者线段树完成，并且需要使用懒惰标记，当查询的时候下放即可，当更新的时候只需要l-r加1即可，判断奇偶就行

判断正反状态

Code:
#include<iostream>

typedef long long ll;
#define Maxn 100005
using namespace std;
ll n,m,a[Maxn],ans[Maxn<<2],tag[Maxn<<2];
long long read(){//快读模板
    long long s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=s*10+(ch-'0');
        ch=getchar();
    }
    return s*w;
}
inline ll ls(ll x) {
    return x << 1;
}
inline ll rs(ll x) {
    return x << 1 | 1;
}
inline void push_up(ll p) {
    ans[p] = ans[ls(p)] + ans[rs(p)];
}
void build(ll p,ll l,ll r) {
    tag[p] = 0;
    if (l == r) {
        ans[p] = a[l];
        return;
    }
    ll mid = (l + r) >> 1;
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
    push_up(p);
}
inline void f(ll p,ll l,ll r,ll k) {
    tag[p] = tag[p] + k;
    ans[p] = ans[p] + k * (r - l + 1);
}
inline void push_down(ll p,ll l,ll r) {
    ll mid = (l + r) >> 1;
    f(ls(p), l, mid, tag[p]);
    f(rs(p), mid + 1, r, tag[p]);
    tag[p] = 0;
}
void update(ll nl,ll nr,ll l,ll r,ll p,ll k) {
    if (nl <= l && r <= nr) {
        ans[p] += k * (r - l + 1);
        tag[p] += k;
        return;
    }
    push_down(p, l, r);
    ll mid = (l + r) >> 1;
    if (nl <= mid)update(nl, nr, l, mid, ls(p), k);
    if (nr > mid) update(nl, nr, mid + 1, r, rs(p), k);
    push_up(p);
}
ll query(ll q_x,ll q_y,ll l,ll r,ll p) {
    ll res = 0;
    if (q_x <= l && r <= q_y)return ans[p];
    ll mid = (l + r) >> 1;
    push_down(p, l, r);
    if (q_x <= mid)res += query(q_x, q_y, l, mid, ls(p));
    if (q_y > mid) res += query(q_x, q_y, mid + 1, r, rs(p));
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    n = read();
    m = read();
    int x, y, k, op;
    while (m--) {
        op = read();
        if (op == 1) {
            x = read();
            y = read();
            update(x, y, 1, n, 1, 1);
        } else {
            x = read();
            if (query(x, x, 1, n, 1) & 1) {
                cout << 1 << '\n';
            } else {
                cout << 0 << '\n';
            }
        }
    }
    return 0;
}

H:djg选美女计划

题目实质上是找男女数量相同的区间，用map存贮第一次出现的男女生差值（男女生数量之差），往后如果出现已经存在的差值，那么这2个相同差值之间的这个区间就是男女生数量相同的。

如样例

0 1 0 0 0 1 1 0 0

-1 0 -1 -2 -3 -2 -1 -2 -3

第7位和第1位差值相同即(1,7]是符合的，共6个。

#include <iostream>
#include <map>
using namespace std;

const int N = 1e5 + 3;
int a[N], ans;
int main() {
    map<int, int> ma;
    int n; cin >> n;
    for (int i = 1, x; i <= n; i++) cin >> x, a[i] = a[i - 1] + (x ? 1 : -1);//三元运算符
    for (int i = 1; i <= n; i++) {
        if (ma[a[i]] == 0) ma[a[i]] = i;
        else ans = max(ans, i - ma[a[i]]);
    }
    cout << ans << endl;
}

I:中间字母

水题

#include <iostream>
using namespace std;

const int N = 1e5 + 3;
int a[N], ans;
int main() {
    int t; cin >> t;
    while (t--) {
        string s; cin >> s;
        cout << s[s.size() / 2] << '\n';
    }
    return 0;
}

J:对M79星云的探索

唯一要注意的是在计算过程中结果需要取余，不然会爆数据，即使是unsigned long long 也不能幸免。

#include <iostream>
using namespace std;

char s[100];
int main() {
    int n, sum = 0;
    cin >> n >> (s + 1);
    for (int i = 1; i <= n; i++) {
        sum = (sum % 114514) * 23;
        if ('0' <= s[i] && s[i] <= '9') sum += s[i] - 48;
        else sum += s[i] - 55;
    }
    cout << sum % 114514 << endl;
    return 0;
}

浙江邮电省赛选拔赛解题报告