9.30~10.5新生赛C~J题

C题 

类似三色问题

原思路是深搜，但会超时

int n, m;
//char mp[2005][2005], ch[3] = { 'R','G','B' };
//bool hv = false;
//bool can[2005][2005][3];
bool check(int r,int c,int i) {
    if (ch[i] == mp[r][c - 1] || ch[i] == mp[r - 1][c]||ch[i]==mp[r-1][c+1]) {
        can[r][c][i] = false;
    }
    else {
        return true;
    }
}
rgb,brg,gbr
//void beg(int r,int c) {
//    if (r == n + 1) {
//        hv = true;
//        return;
//    }
//    if (c == m + 1) {
//        beg(r + 1, 1);
//    }
//    else {
//        for (int i = 0; i <= 2; i++) {
//            if (ch[i] == mp[r][c - 1] || ch[i] == mp[r - 1][c] || ch[i] == mp[r - 1][c + 1]) {
//                continue;
//            }
//                mp[r][c] = ch[i];
//                beg(r, c + 1);
//                if (hv) {
//                    break;
//                }
//            }
//        }
//    }
//
//void p() {
//    for (int i = 1; i <= n; i++) {
//        for (int j = 1; j <= m; j++) {
//            cout << mp[i][j];
//        }
//        cout << endl;
//    }
//}

实验后发现可以遵循这种规律来填数，故直接周期填数 

 /* memset(can, sizeof(can), true);
    cin >> n >> m;
    beg(1, 1);
    p();
  */
    cin >> n >> m;
    string str[3] = { "RGB","BRG","GBR" };
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cout << str[i % 3 ][j % 3 ];
        }
        cout << endl;
    }

D题

没啥好说 

 cin >> n >> sum;
    for (int i = 1; i <= n; i++) {
        cin >> n1 >> n2;
        sum = min(max(sum / n1, 0), max(sum - n2, 0));
    }
    cout << sum;

E题 

  int n, num, count2 = 0, count4 = 0, countc[4] = { 0,0,0,0 };
    char color;
    bool flag = false, flag2 = true;
 
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> num;
        if (num == 2) {
            if (flag||count2>=8) { flag2 = false; break; }
            count2++;
            cin >> color;
            if(color=='R'){
                if (countc[0] >= 2) {
                    flag2 = false;
                    break;
                }
                countc[0]++;
            }   
            if (color == 'Y') {
                if (countc[1] >= 2) {
                    flag2 = false;
                    break;
                }
                countc[1]++;
            }
            if (color == 'B') {
                if (countc[2] >= 2) {
                    flag2 = false;
                    break;
                }
                countc[2]++;
            }
            if (color == 'G') {
                if (countc[3] >= 2) {
                    flag2 = false;
                    break;
                }
                countc[3]++;
            }
        }if (num == 4) {
            if (count4 >= 4) {
                flag2 = false;
                break;
            }
            count4++;
            flag = true;
        }
    }
    if (!flag2) { cout << "No"; }
    else {
        cout << "Yes";
    }

 int cnt = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        //for (int j = 1; j <= m; j++) {
            cin >> arr[i];
        //}
    }
    int beginn, beginm, sum, num;
    bool flag = false;
    cin >> beginn >> beginm >> sum >> num;
    int one;
    bool start = true;
    for (int i = beginn; i <= n; i++) {
        for (int j = 0; j <= m - 1; j++) {
            if (start) { j = beginm - 1; start = false; }
            if (!flag) {
                if ((arr[i][j]-'0') == 0) {
                    continue;
                }
                else {
                    one = (arr[i][j] - '0');
                    flag = true;
                }
            }
            else {
                if (one * 10 + (arr[i][j]-'0') > sum) {
                    cout << one << " ";
                    
                    cnt++;
                    flag = false;
                    
                    if (cnt == num) {
                        break;
                    }
                    if ((arr[i][j] - '0') == 0) {
                        continue;
                    }
                    else {
                        one = (arr[i][j] - '0');
                        flag = true;
                    }
                }
                else {
                    one = one * 10 + (arr[i][j ] - '0');
                }
            }
        }
    }

  int n, m;
    string arr[1005];
    int beginn, beginm, sum, num2;
    bool fi[100];
    int cnt = 0;
    queue<int>q;
    void check(int num) {
        if (num > num2 || fi[num] || num == 0) {
            return;
        }
        else {
            //cout << num<<" ";
            q.push(num);
            fi[num] = true;
            cnt++;
        }
    }
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
            cin >> arr[i];
    }
    
    cin >> beginn >> beginm >> num2 >>sum;
    if (sum > num2) {
        cout << -1;
        return 0;
    }
    int one;
    int j = beginm-1,i=beginn;
    while (i <= n) {
        
        if (j == m - 2) {
            int temp1 = (arr[i][j] - '0') * 10;
            j++;
            int temp2 = (arr[i][j] - '0');
            one = temp1 + temp2;
            i++,j = 0;
            check(one);
        }
        else if (j == m - 1) {
            if (i == n) {
                break;
            }
            int temp1 = (arr[i][j] - '0') * 10;
            i++, j = 0;
            int temp2 = (arr[i][j] - '0');
            one = temp1 + temp2;
            j = 1;
            check(one);
        }
        else if(j<m-2) {
            int temp1 = (arr[i][j] - '0') * 10;
            j++;
            int temp2 = (arr[i][j] - '0');
            one = temp1 + temp2;
            j++;
            check(one);
        }
        if (cnt == sum) {
            break;
        }
    }
    if (cnt < sum) {
        cout << -1;
    }
    else {
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            cout << cur << " ";
       }
    }
        

 long long arr[100005];
    int n, num, op, x, v, cur, cnt, bianhao;
    long long zeng;
    long long sum;
    queue<long long>q;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    cin >> num;
    for (int i = 1; i <= num; i++) {
        cin >> op;  
        if (op == 1) {
            cin >> bianhao>>zeng;
            arr[bianhao] += zeng;
        }
        else if (op == 2) {
            cin >> cur;
            cnt = 1;
            sum = 0;
            while (1) {
                sum += arr[cur];
                arr[cur] = 0;
                if (cur + cnt > n) {
                    break;
                }
                else {
                    cur += cnt;
                    cnt++;
                }
                
            }
            q.push(sum);
        }
    }
    while (!q.empty()) {
        long long t = q.front();
        q.pop();
        cout << t << endl;
    }

int n;
    long long xi, yi;
    long double pk, px, py;
    bool valid = true;
    cin >> n;
    if (n <= 2) {
        cout << -1;
    }
    else {
        for (int i = 1; i <= n; i++) {
            cin >> xi >> yi;
            if (i == 1) { px = xi; py = yi; continue; }
            if (i == 2) { pk = (long double)(yi - py) /(long double) (xi - px); continue; }
            if ((yi - py) / (xi - px) != pk) {
                cout << "Parabola";
                valid = false;
                break;
            }
        }
        if (valid) {
            
            if (pk == 0) {
                cout << "Const";
            }
            
            else {
                cout << "Line";
            }
        }
    }

#include<iostream>
#include<stack>
#include<string>
using namespace std;
 
int n;
int main() {
    cin >> n;
    while (n--) {
        stack<int>s;
        string st;
        cin >> st;
        int i = 0;
        for (; i < st.length(); i++) {
            if (st[i] == '{') {
                if (!s.empty()) {
                    if (s.top() == ')' || s.top() == ']' || s.top() == '>') {
                        cout << "NO" << endl;
                        break;
                    }
                }
                s.push('}');
            }
            else if (st[i] == '(') {
                if (!s.empty()) {
                    if (s.top() == '>') {
                        cout << "NO" << endl;
                        break;
                    }
                }
                s.push(')');
            }
            else if (st[i] == '[') {
                if (!s.empty()) {
                    if (s.top() == ')' || s.top() == '>') {
                        cout << "NO" << endl;
                        break;
                    }
                }
                s.push(']');
 
            }
            else if (st[i] == '<') {
                s.push('>');
 
            }
 
            if (s.empty()) {
                cout << "NO" << endl;
                break;
            }
            else if (st[i] == s.top()) {
                s.pop();
            }
        }
            if (s.empty() && i == st.length()) {
                cout << "YES" << endl;
            }
        }
    
}

 string s1;;
    stack<int>s;
    int sum, top = 0, num1, num2;
 
    getline(cin, s1);
    for (int i = 0; s1[i] != '#'; i++) {
        if (s1[i] >= '0' && s1[i] <= '9') {
            sum = s1[i] - '0';
            int j;
            for (j = i + 1; s1[i] != '#'; j++) {
                if (s1[j] >= '0' && s1[j] <= '9') {
                    sum = sum * 10 + (s1[j] - '0');
                }
                else {
                    break;
                }
            }
            if (i > 0 && s1[i - 1] == '-') {
                sum = -sum;
            }
            i = j - 1;
            
            s.push(sum);
            top++;
           
        }
        else if (s1[i]==' ') {
            continue;
        }
        else if (s1[i]=='-'&&s1[i+1]!=' ') {
            continue;
        }
        else {
            if (top < 2) {
                cout << "Expression Error: " << s.top() << endl;
                return 0;
            }
            num1 = s.top();
            s.pop();
            top--;
            num2 = s.top();
            s.pop();
            top--;
            switch (s1[i]) {
            case '+':
 
                
                s.push(num2 + num1);
                top++;
                break;
            case '-':
                s.push(num2 - num1);
                top++;
                break;
            case '*':
                s.push(num2 * num1);
                top++;
                break;
            case '/':
                if (num1 == 0) {
                    cout << "Error: " << num2 << "/0" << endl;
                    return 0;
                }
                s.push(num2 / num1);
                top++;
                break;
            }
        }
    }
    if (top != 1) {
        cout << "Expression Error:  " << s.top() << endl;
    }
    else {
        cout << s.top() << endl;
    }

  int n;
    long long k;
    string t;
    vector<char>words;
    void swap(int a, int b) {
        char temp = t[a];
        t[a] = t[b];
        t[b] = temp;
    }
    cin >> n >> k;
    cin >> t;
    //cout << t << endl;
    int len = 0;
    for (int i = 0; i < 4 * n; i++) {
        if (t[i] == '0') {
            len++;
        }
        if (t[i] == '1') {
            if (k <= len) {
                swap(i, i - k);//i是当前的位置，k是能支撑交换的长度
                break;
            }
            else {
                swap(i, i - len);
                k -= len;
            }
        }
    }
    //cout << t << endl;
    for (int i = 0; i < 4 * n; i=i+4) {
        int temp = 0;
        for (int j = 3; j >= 0; j--) {
            temp += (t[i + j]-'0') * pow(2, 3 - j);
        }
        words.push_back('A'+temp);
    }
    //就是说直接在原来的01序列上，让第一个1不断往前移，一直积累，直到用完k次
    //如果从头开始遍历，遇到0，就积累进步长，遇到1，就是后续的第一个1，就要消耗k来进行移动
    //此时这个1前的0数量就是已经积累的步长，如果k大于，就让k减去，并能让这个1移到前面
    //如果小于，则只能移一点，并且终止
    for (int i = 0; i < words.size(); i++) {
        cout << words[i];
    }

#include<stdio.h>
#include<iostream>
#include<string>
#include<stack>
#include<vector>
#include<cmath>
#include<queue>
using namespace std;
int n, m;
int t,mod=1e9+7;
const int N = 1e3;
int c[N][N], dp[N][N];
//s中的每个元素是一组A的集合，这个A的集合满足里面集合的元素是连续子集的关系
//m是说s里的每个元素所包含的A的数量，衡量s里的每个元素
//N是说每个A的大小
//要连续M个A连续成子集，才能组成一个元素
//一种极端是M个A都相等，
//这里A指的是大A的子集
//M指向下取连续子集的次数
// 而且这种向下取是不可逆的，即这次取完后，剩下的都得在此基础上接着往下取，即此时母集就是这个
// 递归，这一层从母集取的子集是下一层的母集
// 如果母集有n个元素，那么子集的元素个数有0~n种情况
// 每次取的情况都能唯一确定一个情况
// 如果取n个，那就有1种
// n-1,有n种
// 组合数
// 如果取0个，那么后续都只能取0个，即此时后续都是空集
// 在母集取，确定这层取的子集个数
// 然后这层的子集个数是下层的母集个数
// 如果让每层递归返回这层母集的所有情况数
// 那么这层就是要让取的子集个数的情况数*对应个数的下一层母集的所有情况数
// 最后加和
// 
// 如n=2,m=1,只能向下取一次
// 母集有2个，则子集可以取2，1，0个
// 取2个时有一种情况，取1个时有两种情况，取0个时有1种情况
// 每次取完后都不再向下取，因为只能向下取一次，即递归层数为1
// 直接加和，为4种
// 
// 如果n=1,m=100,能向下取100次
// 母集只有1个元素，则子集可以取1，0个
// 取1个时，一种情况，再向下
//
// //
// 从头开始，即从空集开始，一串0，长度为n
// 然后就每次对于为0的地方可以有，也可以没有
// 如果选择有，就是0变成1，如果没有就依然保持0
// 
//就是手里的n是一定的，然后一共可以操作m次
//每次可以丢掉不大于当前手里数量的个数
//问丢的所有情况数是多少
// 
// 有两个参数，一个是当前剩的数量，一个是还剩下的操作次数
// 应该让操作次数从0一直到m，即补全而不超过的思想
// 每次可以选择补，也可以选择不补
// 补的话，就是在和全部相比，剩下的那些数里选
// 并且确定要补的个数，每次补的选择总数就是组合数
// 
//
//dpr,c记录剩这么多，且还有这么多次数时，一共可能的情况
 
//dp[0][c]=0,如果是空集的话，不管剩几次，都是0
int fc(int n,int up) {
    if (c[n][up]) {
        return c[n][up];
    }
    for (int i = 0; i <= n; i++) {
        c[i][1] = i % mod;
        c[i][i] = c[i][0] = 1;
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j < i; j++) {
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
        }
    }
    return c[n][up];
}
 
int fdp(int r, int cn) {//r是说当前剩余，c是说还剩下的操作次数
    if (dp[r][cn]) {
        return dp[r][cn];
    }
    if (cn == 0) {//没有时，即最后一个元素里的最后A
        dp[r][cn] = 1;
        return dp[r][cn];
    }
    else {
        for (int i = 0; i <= r; i++) {//i是说下层母集的长数,从原母集中丢掉了r-i个元素，要选择
            //前者是说选完后的子集是下一层的母集，并由此确定的后续情况总数
            //后者是说在本次选的情况的总数
            dp[r][cn] += (fdp(i, cn - 1) * fc(r, r - i))%mod;
        }
       
        return dp[r][cn];
    }
  
}
int main() {
    cin >> t;
    while (t--) {
        cin >> n >> m;
        cout << fdp(n, m) << endl;
    }
 
    return 0;
}

每个十进制数都可以转换为二进制，也就是都可以用2的次幂组合得到

 int t;
    long long n, m, ans, base;
    long long mod = 1e9 + 7;
    long long quick(long long a, long long b) {//a的b次方
        //b是一个十进制数，把b转为二进制，然后组合
        //就是说a的不同b的独位上的数乘起来，保证每个独位上最多只有一个
        ans = 1;
        while (b > 0) {
            if (b & 1) {
                ans = ans * base % mod;
            }
            base = base * base % mod;
            b >>= 1;
        }
        return ans;
    }
    //第二个思路是递归，就是偶数时，就是x^p=x^(2*(p/2))
    //就是让底数自乘一下，底数变大了，指数缩小了一半
    //如果是奇数时，依然是自乘，指数缩小一半，但是最后算完还要再乘以个原底数
    cin >> t;
    while (t--) {
        cin >> n >> m;
        base = m + 1;
        cout <<quick(m+1, n) << endl;
    }

 struct node {
        int data;
        long long sum;
        double wait;
        int pre;
        double ex;
        bool have = false;
    }list[N];
    int n;
    long long sum1;
    void fuzhi(int i) {
        sum1 = 0;
        for (int j = 1; j <= n; j++) {
            if (j == i) { continue; }
            else if (list[j].pre == list[i].pre) {
                sum1 += list[j].sum;
            }
        }
        list[i].wait = (double)sum1 / 2.0 + list[list[i].pre].wait;
        list[i].ex = list[i].wait + (double)list[i].sum;
        list[i].have = true;
 
        //cout << list[i].sum << " " << list[i].wait << " " << " " << list[i].ex << endl;
    }
    cin >> n;
    list[1].pre = 0;
    list[1].have = true;
    for (int i = 1; i <= n; i++) {
        cin >> list[i].data;
        list[i].sum = list[i].data;
    }
    for (int i = 1; i <= n - 1; i++) {
        int f, b;
        cin >> f >> b;
        list[b].pre = f;
        int p = f;
        while (p != 0) {
            list[p].sum += list[b].data;
            p = list[p].pre;
        }
    }
    fuzhi(1);
    cout << fixed << setprecision(2) << list[1].ex << " ";
    for (int i = 2; i <= n; i++) {
        if (list[i].have) {
            printf("%.2lf ", list[i].ex);
          //  cout << fixed << setprecision(2)<< list[i].ex << " ";
            continue;
        }
 
        stack<int>s;
        int temp = i;
        while (!list[list[i].pre].have) {
            s.push(i);
            i = list[i].pre;
        }
        fuzhi(i);
        while (!s.empty()) {
            int cur = s.top();
            s.pop();
            fuzhi(cur);
        }
        i = temp;
 
        printf("%.2lf ", list[i].ex);
       // cout << fixed << setprecision(2)<<list[i].ex << " ";
    }

//void link(int x, int y) {//x是当前的结点，y是连接到这个结点的子节点
//    to[++m] = y;//x结点的第++m个孩子结点为y
//    next[m] = fi[x];//fi[x]是之前的m，就是这个新结点的前一个结点，或许可以称为新节点的前驱结点
//    fi[x] = m;//记录的不仅是数量，还是最后一个孩子的编号
//}//是说每个结点都存着一个数组，这个数组把子节点串起来，且子节点满足兄弟关系
那么每个子节点的串的关系就用next来表述，子节点有子节点的编号，被串起来时，是父节点数组的编号，即m，
每个子节点

应该写层序优先