题目描述

blablabla

样例

/*
对于70%数据的读取没有想到好的方法，所以目标是做40%
*/

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

int n, m;
const int N = 2510, M = 510, null = 0x3f3f3f3f;//null for N/A
char ch[N];
struct node{
    int dn;
    int attr[M];// 0x3f3f3f3f or val
}p[N];

bool cmp(node s1, node s2){
    return s1.dn < s2.dn;
}

bool isSuitable(int i, int a, char op, int c){
    if(op == ':'){
        if(p[i].attr[a] == c) return true;
    }else{// ~
        if(p[i].attr[a] != null && p[i].attr[a] != c) return true;
    }
    return false;
}

int main(){
    cin >> n;
    int t;
    for(int i = 0; i < n; i++){
        cin >> p[i].dn >> t;//输入多个需要用scanf，这里较少
        memset(p[i].attr, 0x3f, sizeof p[i].attr);
        while(t--){
            int data, val;
            cin >> data >> val;
            p[i].attr[data] = val;
        }
    }
    sort(p, p + n, cmp);//sorted by dn

    cin >> m;
    while(m--){
        scanf("%s", ch);
        if(ch[0] == '&' || ch[0] == '|'){ //easy expr
            int a, b, c, d;
            char op, op1, op2;
            sscanf(ch, "%c(%d%c%d)(%d%c%d)", &op, &a, &op1, &b, &c, &op2, &d);
            if(op == '&'){
                for(int i = 0; i < n; i++){
                    if(isSuitable(i, a, op1, b) && isSuitable(i, c, op2, d)) cout << p[i].dn << ' ';
                }
            }else{// |
                for(int i = 0; i < n; i++){
                    if(isSuitable(i, a, op1, b) || isSuitable(i, c, op2, d)) cout << p[i].dn << ' ';
                }
            }
        }else{ //base expr
            int a, c;
            char op;
            sscanf(ch, "%d%c%d", &a, &op, &c);
            for(int i = 0; i < n; i++){
                if(isSuitable(i, a, op, c)) cout << p[i].dn << ' ';
            }
        }
        puts("");
    }


    return 0;
}```


----------

### 算法1
##### (暴力枚举)  $O(n^2)$

blablabla

#### 时间复杂度

#### 参考文献

#### C++ 代码

blablabla

----------

### 算法2
##### (暴力枚举)  $O(n^2)$

blablabla

#### 时间复杂度

#### 参考文献


#### C++ 代码

blablabla
```

题目描述

暴力70分

样例

/*
暴力做法；
数组存放(ti, ci)，每次循环先sort(flag, ti降序，ci升序)，若存在，m -= ci, ti -= 1
这里的flag意思是若t1 <= k，flag = 0, 排序放到后面
若不存在，return 排序好后的arr[0].t1即T_total
时间复杂度为：m * sort
至此，csp系统里是70分，AcWing只过了3个数据；
*/

#include<iostream>
#include<algorithm>
#include<utility>

using namespace std;

int n, m, k;
const int N = 100010;
struct node{
    int t, c, flag;
}p[N];

bool cmp(node s1, node s2){//flag = 1, 若s的ti <= k, 则他的flag = 0
    if(s1.flag != s2.flag) return s1.flag > s2.flag;
    else if(s1.t != s2.t) return s1.t > s2.t;
    else return s1.c < s2.c;
}

int main(){
    cin >> n >> m >> k;

    for(int i = 0; i < n; i++){
        cin >> p[i].t >> p[i].c;
        p[i].flag = p[i].t > k ? 1 : 0;
    }

    while(m > 0){
        sort(p, p + n, cmp);
        if(p[0].flag == 0) break;//已经调整好
        else{
            if(m > p[0].c) m -= p[0].c;
            else break;
            p[0].t--;
            if(p[0].t == k) p[0].flag = 0;
        }
    }
    sort(p, p + n, cmp);
    cout << p[0].t;

    return 0;
}

二分100分

/*
暴力做法；
数组存放(ti, ci)，每次循环先sort(flag, ti降序，ci升序)，若存在，m -= ci, ti -= 1
这里的flag意思是若t1 <= k，flag = 0, 排序放到后面
若不存在，return 排序好后的arr[0].t1即T_total
时间复杂度为：m * sort
至此，csp系统里是70分，AcWing只过了3个数据；

因为m是10^9，所以肯定过不了，改进想法是如果对于每个(ti, ci)，都能快速求出ti减去的数量，时间复杂度就和m无关了
二分，全都缩小到x天, [k, p[0].t], 
check: sum((p[i].t - x) * p[i].c) <= m，这里注意需要用long long
这样结束，csp里100分
*/

#include<iostream>
#include<algorithm>

using namespace std;

int n, m, k;
const int N = 100010;
struct node{
    int t, c;
}p[N];

bool check(int u){
    long long res = 0;
    for(int i = 0; i < n; i++){
        if(p[i].t <= u) continue;
        res += (p[i].t - u) * p[i].c;
    }
    if(res <= m) return true;
    else return false;
}

int b_search(int max_t){
    int l = k, r = max_t;
    while(l < r){
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main(){
    cin >> n >> m >> k;

    int max_t = 0;
    for(int i = 0; i < n; i++){
        cin >> p[i].t >> p[i].c;
        max_t = max(max_t, p[i].t);
    }
    cout << b_search(max_t);

    return 0;
}

题目描述

blablabla

样例

#include<iostream>
#include<algorithm>

using namespace std;

int n, a, b;
int res;

int main(){
    cin >> n >> a >> b;

    int x1, y1, x2, y2;
    for(int i = 0; i < n; i++){
        cin >> x1 >> y1 >> x2 >> y2;
        //(x1, y1)和(0, 0)比较，(x2, y2)和(a, b)比较
        if(x1 < 0) x1 = 0;
        if(x1 > a) x1 = a;
        if(y1 < 0) y1 = 0;
        if(y1 > b) y1 = b;
        if(x2 < 0) x2 = 0;
        if(x2 > a) x2 = a;
        if(y2 < 0) y2 = 0;
        if(y2 > b) y2 = b;
        res += (y2 - y1) * (x2 - x1);
    }
    cout << res;

    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

#include<iostream>
#include<algorithm>

using namespace std;

int n, a, b;
int res;

int main(){
    cin >> n >> a >> b;

    int x1, y1, x2, y2;
    for(int i = 0; i < n; i++){
        cin >> x1 >> y1 >> x2 >> y2;
        //(x1, y1)和(0, 0)比较，(x2, y2)和(a, b)比较
        if(x1 < 0) x1 = 0;
        if(x1 > a) x1 = a;
        if(y1 < 0) y1 = 0;
        if(y1 > b) y1 = b;
        if(x2 < 0) x2 = 0;
        if(x2 > a) x2 = a;
        if(y2 < 0) y2 = 0;
        if(y2 > b) y2 = b;
        res += (y2 - y1) * (x2 - x1);
    }
    cout << res;

    return 0;
}

/*
f(1)即 <= 1的最大数的下标，即0
f(2)即 <= 2的最大数的下标，即1
时间限制是0.3s, 所以时间复杂度控制在10^6 - 10^7之间
最左边边界为0， 最右边边界为N, 小于输入的第一个数的不需要计算，因为下标是0，对res没有影响
*/

#include<iostream>
#include<algorithm>

using namespace std;

int n, N;
int res;
int d, pre;

int main(){
    cin >> n >> N;

    cin >> pre;
    for(int i = 1; i < n; i++){
        cin >> d;
        res += (d - pre) * i;
        pre = d;
    }
    res += (N - pre) * n;
    cout << res;

    return 0;
}

题目描述

blablabla

样例

/*
f(1)即 <= 1的最大数的下标，即0
f(2)即 <= 2的最大数的下标，即1
时间限制是0.3s, 所以时间复杂度控制在10^6 - 10^7之间
最左边边界为0， 最右边边界为N, 小于输入的第一个数的不需要计算，因为下标是0，对res没有影响
*/

#include<iostream>
#include<algorithm>

using namespace std;

int n, N;
int res;
int d, pre;

int main(){
    cin >> n >> N;

    cin >> pre;
    for(int i = 1; i < n; i++){
        cin >> d;
        res += (d - pre) * i;
        pre = d;
    }
    res += (N - pre) * n;
    cout << res;

    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

#include<iostream>

using namespace std;

int n, k;
const int N = 1e5 + 10;
int h[N];
int res;

int main(){
    cin >> n >> k;

    int a, b;
    h[0] = 1;
    for(int i = 0; i < k; i++){
        cin >> a >> b;
        if(h[b] == 0){
            res++;
        }
        h[a] = 1;
    }
    cout << res;

    return 0;
}

题目描述

模拟

样例

/*
s: 50 * 50
l: 10^9
n: 1000

0.5s : 10^6 - 10^7

遍历(L + 1) * (L + 1)的地图，check ，如果01都相同，cnt++；时间复杂度为l*l*l*s*s
因为藏宝图左下角一定是树，所以遍历每棵树n，check为n*s*s，时间复杂度为n*n*s*s，即40%
注意这里的(0,0)是左下角
预处理所有左下角对应的图，gt[N][M][M], chekc时遍历gt[i]即可，check时间复杂度为n*s*s, ac
*/

#include<iostream>
#include<algorithm>
#include<cstring>
#include<utility>

using namespace std;

typedef pair<int, int> PII;

int n, l, s;
const int N = 1010, M = 55;
int g[M][M], gt[N][M][M];//gt for check
PII p[N];
int res;

bool check(int u){
    for(int i = 0; i <= s; i++){
        for(int j = 0; j <= s; j++){
            if(gt[u][i][j] != g[i][j]){
                return false;
            }
        }
    }
    return true;
}

int main(){
    cin >> n >> l >> s;
    for(int i = 1; i <= n; i++) cin >> p[i].first >> p[i].second;
    for(int i = s; i >= 0; i--){//上下翻转
        for(int j = 0; j <= s; j++){
            cin >> g[i][j];
        }
    }

    for(int i = 1; i <= n; i++){//n*n
        int gt_x = p[i].first, gt_y = p[i].second;
        for(int j = 1; j <= n; j++){
            int x = p[j].first - gt_x, y = p[j].second - gt_y;
            if(x < 0 || y < 0 || x > s || y > s) continue;
            gt[i][x][y] = 1;
        }
    }

    for(int i = 1; i <= n; i++){
        int x = p[i].first, y = p[i].second;
        if(x + s > l || y + s > l) continue;
        //check
        if(check(i)) res++;
    }
    cout << res;

    return 0;
}

/*
模拟题
*/

#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;

int n;
const int N = 1010;
double h[N], t[N];//t[i]即ai - avg
double avg, Std;

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> h[i];
        avg += h[i];
    }
    avg /= n;

    for(int i = 1; i <= n; i++){
        t[i] = h[i] - avg;
        Std += t[i] * t[i];
    }
    Std /= n;
    Std = sqrt(Std);

    for(int i = 1; i <= n; i++){
        cout << t[i] / Std << endl;
    }

    return 0;
}

题目描述

01背包

样例

/*
01背包
选择若干本书，使sum - x最大，sum是书的价值之和
同01背包模板，容量最大是sum - x, 价值是w[i], 容积也是w[i]
f[i][j]即前i本，价值为j的最大值
f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + w[i]);
还可以优化为一维，略过;
*/

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

int n, x;
const int N = 35, M = 5e5;
int f[N][M], w[N];

int main(){
    cin >> n >> x;

    int sum = 0;
    for(int i = 1; i <= n; i++){
        cin >> w[i];
        sum += w[i];
    }

    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= sum - x; j++){
            f[i][j] = f[i - 1][j];
            if(j >= w[i]) f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + w[i]);
        }
    }
    cout << sum - f[n][sum - x];

    return 0;
}