#include <bits/stdc++.h>
#include <cstdio>
#include <string>
using namespace std;
const int N = 1000010;
int sa[N];  // 求Alice 出现的坐标标示为1 当一个Bob出现求sa[l ~ r]

int main()
{
    int k;
    string str;
    cin >> k;
    getchar();
    getline(cin, str);
    long long res = 0;

    for (int i = 0; i < str.size(); i++) {
        i = str.find("Alice", i);
        if (i == string::npos)
            break;
        if ((i + 5 < str.size() && isalpha(str[i + 5])) || (i >= 1 && isalpha(str[i - 1]))) {
            i = i + 5;
            continue;
        }
        sa[i + 1] = true;
    }

    for (int i = 1; i <= str.size(); i++) {
        sa[i] += sa[i - 1];
    }

    for (int i = 0; i < str.size(); i++) {
        i = str.find("Bob", i);
        if (i == string::npos)
            break;

        if ((i + 3 < str.size() && isalpha(str[i + 3])) || (i >= 1 && isalpha(str[i - 1]))) {
            i = i + 3;
            continue;
        }
        // A ... Bob ... A  //坐标后面要加1 s[]数组偏移了
        int l = max(0, i - k - 5) + 1, r = min(i + 3 + k + 1, (int)str.size());

        res += sa[r] - sa[l - 1];
    }

    cout << res << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010, mod = 1e9 + 9;
ll sz[N], d[N];
ll n;
int fact[N], infact[N];
int C(int a, int b)
{
    return (ll)fact[a] * infact[a - b] % mod * infact[b] % mod;
}
int qmi(int a, int b)
{
    ll res = 1;
    while (b) {
        if (b & 1)
            res = res * a % mod;
        a = (ll)a * a % mod;
        b >>= 1;
    }

    return res;
}
void init()
{
    fact[0] = 1;
    infact[0] = 1;
    for (int i = 1; i < N; i++) {
        fact[i] = (ll)fact[i - 1] * i % mod;
        infact[i] = (ll)infact[i - 1] * qmi(i, mod - 2) % mod;
    }
}

int dp(int i)
{
    if (sz[i] <= 1)
        return 1;
    int l = 2 * i, r = 2 * i + 1;
    // int fl = dp(l),fr = dp(r);
    // cout<<i<<" "<<l<<" "<<r<<endl;
    // cout<<"---"<<sz[i] - 1<<" "<<sz[l]<<" "<<fl<<" "<<fr<<endl;
    // int res = (ll)C(sz[i] - 1, sz[l]) * fl % mod * fr % mod;
    // cout<<i<<" "<<res<<endl;
    return (ll)C(sz[i] - 1, sz[l]) * dp(l) % mod * dp(r) % mod;
}
int main()
{
    cin >> n;
    for (int i = n; i >= 1; i--) {
        sz[i] = 1;
        int l = 2 * i, r = 2 * i + 1;
        if (l <= n)
            sz[i] += sz[l];
        if (r <= n)
            sz[i] += sz[r];
    }
    //for(int i = 1;i <= n;i++) cout<<sz[i]<<endl;
    init();  // 初始化C(a,b);
    cout << dp(1) << endl;
    return 0;
}

公式法

$$p^2+(e*d-n-2)p+n$$
一个正解为:
$$\frac{-b + \sqrt{b^2-4\times{a}\times{c}}}{2\times{a}}$$

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
int main()
{
    int T;
    cin>>T;
    while(T--){
        ll e,d,n;
        cin>>n>>d>>e;
        ll b = -(n - e*d + 2),c = n;
        if(b*b < 4*c){//无解
            cout<<"NO"<<endl;
        }else{
            ll deta = (ll)sqrt(b*b - 4*c);
            ll temp = deta*deta;
            if(temp == (b*b - 4*c)){
                ll p = (-b + deta)/2;
                ll q = n/p;
                cout<<min(p,q)<<" "<<max(p,q)<<endl;
            }else{
                cout<<"NO"<<endl;
            }

        }
    }
    return 0;
}

二分

$$p + q = m $$
$$p\times{q} = m$$

设q为较小数,则$q\in[1,m >> 1]$,由y = x(m - x)函数可知,y在{1,m >> 1}中单调递增

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
int main()
{
    int T;
    cin>>T;
    while(T--){
        ll e,d,n;
        cin>>n>>d>>e;
        ll m = n - e*d + 2;
        ll l = 1,r = m >> 1;
        while(l < r){
            ll mid = l + r >> 1;
            if(mid * (m - mid) >= n) r = mid;
            else l = mid + 1;
        }

        if(l * (m - l) == n){
            cout<<l<<" "<<m - l<<endl;
        }else{
            cout<<"NO"<<endl;
        }
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e9;
long long qmi(long long a,long long b)
{
    if(a >= 10 && b >= 10) return -1;
    long long res = 1;
    while(b){
        if(b&1) res = res*a;
        if(res > N) return -1;
        a = a*a;
        b >>= 1;
    }
    if(res > N) return -1;
    return res;
}
int main()
{
    long long a,b;
    cin>>a>>b;
    cout<<qmi(a,b)<<endl;
}

模拟

1. 将每个数字存入一个字符串
2. 找规律填入每个数字(每次填入一个宽度)

#include <bits/stdc++.h>
#include <climits>
#include <string>
using namespace std;
const int N = 1010;
char g[N][N];
void slove(int n)
{
    memset(g, 0, sizeof g);
    string s = "";
    int sz = 4 * n - 4;
    for (int i = 1;; i++) {
        if (s.size() >= sz)
            break;
        s += to_string(i);
    }
    cout << s << endl;


    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n + i - 1; j++) {
            g[i][j] = '.'; // 填入每一个'.'
        }
        g[i][n - i + 1] = s[cnt++];//左边的腰
    }

    for (int i = 2; i <= 2 * n - 1; i++) //底
        g[n][i] = s[cnt++];

    for (int i = n - 1, j = 2 * n - 2; i >= 2; i--, j--)
        g[i][j] = s[cnt++];//右边的腰

    for (int i = 1; i <= n; i++) {
        printf("%s\n", g[i] + 1);
    }
}
int main()
{
    int n;
    while (cin >> n) {
        slove(n);
    }
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 200010;
int h[N],ne[N],e[N],idx;
int f[N];
int n,m;
void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
int dp(int u,int fa)
{
    f[u] = 0;
    int cnt = 0,res = 0;
    for(int i = h[u];i != -1;i = ne[i]){
        int j = e[i];
        if(j == fa) continue;
        cnt++;
        res = max(res,dp(j,u));
        //cout<<j<<" "<<f[j]<<endl;
    }
    return f[u] = res + cnt;
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n;
    for(int i = 2;i <= n;i++){
        int b;
        cin>>b;
        add(b,i),add(i,b);
    }
    cout<<dp(1,-1)<<endl;
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1010;
int a[N][N];
PII node[N];
unordered_map<LL,int> st;
int n,S;
int l;
LL get(int x,int y){
    return (LL)x*(l+1)+y;
}
bool check(int idx)
{
    int x = node[idx].first,y = node[idx].second;
    for(int i = 0;i <= S;i++){
        for(int j = 0;j <= S;j++){
            int tx = x + i,ty = y + j;
            if(tx > l || ty > l) return false;
            if(st.count(get(tx,ty)) != a[i][j]) return false;
        }
    }
    return true;
}
int main()
{
    cin>>n>>l>>S;
    for(int i = 0;i < n;i++){
        int x,y;
        cin>>x>>y;
        node[i].first = x;
        node[i].second = y;
        st[get(x,y)] = true;
        // cout << get(x,y)<<endl;
    }
    for(int i = S;i >= 0;i--){
        for(int j = 0;j <= S;j++){
            cin>>a[i][j];
        }
    }
    int res = 0;
    for(int i = 0;i < n;i++){
        if(check(i)){
            res++;
        }
    }
    cout<<res;
    return 0;

}

暴力全排列枚举

#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int g[N][N];
int cnt,st[N];
int m;
int backup[N][N],res[N][N];
void check(int a[])
{
    for(int i = 0,k = 0;i < 3;i++){
        for(int j = 0;j < 3;j++){
            if(g[i][j]) backup[i][j] = g[i][j];
            else backup[i][j] = a[k++];
        }
    }

    int s = backup[0][0] + backup[0][1] + backup[0][2];
    if(s != 15) return;
    s = backup[1][0] + backup[1][1] + backup[1][2];
    if(s != 15) return;
    s = backup[2][0] + backup[2][1] + backup[2][2];
    if(s != 15) return;

    s = backup[0][0] + backup[1][0] + backup[2][0];
    if(s != 15) return;
    s = backup[0][1] + backup[1][1] + backup[2][1];
    if(s != 15) return;
    s = backup[0][2] + backup[1][2] + backup[2][2];
    if(s != 15) return;

    s = backup[0][0] + backup[1][1] + backup[2][2];
    if(s != 15) return;

    s = backup[0][2] + backup[1][1] + backup[2][0];
    if(s != 15) return;

    cnt++;
    if(cnt == 1){
        for(int i = 0,k = 0;i < 3;i++){
            for(int j = 0;j < 3;j++){
                res[i][j] = backup[i][j];
            }
        }
    }
    return;
}
int main()
{
    for(int i = 0;i < 3;i++){
        for(int j = 0;j < 3;j++){
            cin>>g[i][j];
            if(g[i][j]) st[g[i][j]] = true;
        }
    }


    int num[N];
    for(int i = 1;i <= 9;i++){
        if(!st[i])  num[m++] = i;
    }


    //for(int i = 0;i < m;i++) cout<<num[i]<<endl;
    do{
        check(num);
        if(cnt >= 2){
            cout<<"Too Many"<<endl;
            return 0;
        }
    }while(next_permutation(num,num + m));

    for(int i = 0;i < 3;i++){
        for(int j = 0;j < 3;j++){
            cout<<res[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <cstring>
using namespace std;
const int N = 300010;
int d[N];
int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    for(int i = 1;i <= n;i++){
        int t,c;
        cin>>t>>c;
        d[max(1,t - c + 1)]++,d[t + 1]--;
    }
    for(int i = 1;i < N;i++){
        d[i] += d[i - 1];
    }
    for(int i = 0;i < m;i++){
        int q;
        cin>>q;
        cout<<d[q + k]<<endl;
    }
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 300010;
int f[N];
int n,m;
int main()
{
    cin>>n>>m;
    f[0] = 1;
    for(int i = 0;i < n;i++){
        int w;
        cin>>w;
        for(int j = N;j >= w;j--){
            f[j] |= f[j - w];
        }
    }

    for(int i = m;i < N;i++){
        if(f[i]){
            cout<<i<<endl;
            return 0;
        }
    }
}