统计子矩阵

解释res += r - l + 1
每次累加左边界和右边界之间有多少个元素

#include <iostream> 
using namespace std;
typedef long long LL;
const int N = 510;
int s[N][N], k, n, m; 
int main(){
    cin>>n>>m>>k;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            scanf("%d", &s[i][j]), s[i][j] += s[i-1][j];//求每一列的前缀和
    LL res=0;
    for(int i=1; i<=n; i++){//上边界i
        for(int j=i; j<=n; j++){//下边界j
            for(int l=1, r=1, sum=0; r<=m; r++){//二分
                sum += s[j][r] - s[i-1][r];
                while(l<=r && sum>k){
                    sum -= s[j][l] - s[i-1][l];
                    l++;
                }
                res += r - l + 1;
            }
        }
    }
    cout<<res<<endl;
    return 0;
}

bilibi

子串分值和

s[i]至少的贡献值为1（它本身），至多到上一次出现s[i]位置之间的元素个数，即i - lta[s[i]]
故f[i]=f[i−1]+i−pos

#include <iostream>
#include <cstring> 
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
//lta[i]表示s[i]上一次出现的位置
//f[i]表示以s[i]为结尾的所有子串的总分值
int lta[200], f[N];
string s;
int main()
{
    cin>>s;
    s = ' ' + s;
    int len = s.size();
    LL res = 0;
    for(int i=1; i<len; i++){
        f[i] = f[i-1] + i - lta[s[i]];
        lta[s[i]] = i;
        res += f[i];
    }
    cout<<res<<endl;
    return 0;
}

回文日期

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
string date;

bool check_year(int year){//判断闰年 
    return year % 400 == 0 || year % 4 == 0 && year % 100 != 0;
}

bool check(string s, int year){//判断回文日期和ABABBABA型的日期合法性
    string month = s.substr(0,2);
    int m = stoi(month);
    string day = s.substr(2,4);
    int d = stoi(day);

    if(m == 2){
        if(check_year(year))
            return m >= 1 && m <=12 && d >= 1 && d <= months[m]+1;
        else return m >= 1 && m <=12 && d >= 1 && d <= months[m];
    }else return m >= 1 && m <=12 && d >= 1 && d <= months[m];
}

int main()
{
    cin>>date;
    string cur_y = date.substr(0,4);
    string cur_md = date.substr(4,8);
    bool st1 = false, st2 = false;
    for(int i=stoi(cur_y); i<=9999; i++){
        string s1 = to_string(i);
        string s2;
        for(int j=s1.size()-1; j>=0; j--) s2.push_back(s1[j]);
        if(s1+s2 <= date) continue;//卡
        if(check(s2, i) && !st1){
            st1 = true;
            cout<<s1 + s2<<endl;
        }
        if(s1[0] == s1[2] && s1[1] == s1[3] && 
        s1[0] != s1[1] && check(s2, i) && !st2){
            st2 = true;
            cout<<s1 + s2<<endl;
            break;
        }
    }
    return 0;
}

A 市的车牌由六位组成, 其中前三位可能为数字 0 至 9 , 或者字母 AA 至 FF, 每位有 16 种可能。后三位只能是数字 0 至 9。为了减少攀比, 车牌中不能有连 续三位是相同的字符。

例如, 202020 是合法的车牌, AAA202 不是合法的车牌, 因为前三个字 母相同。

请问, A 市有多少个合法的车牌?

排列组合+筛除不合法车牌

#include <iostream>
#include <vector>
using namespace std;
vector<int> v;
int cnt;
void dfs(int n){
    if(n == 6){
        bool flag = false;
        for(int i=0; i+2<v.size(); i++){
            if(v[i] == v[i+1] && v[i] == v[i+2]){
                flag = true;
                break;
            }
        }
        if(!flag) cnt++;
    }
    else{
        int k = n < 3 ? 15 : 9;
        for(int i=0; i<=k; i++){
            v.push_back(i);
            dfs(n+1);
            v.pop_back();
        }
    }
}
int main(){
    dfs(0);
    cout<<cnt<<endl;
    return 0;
}

问题描述
小蓝定义了一个 Fibonacci 集合 F，集合的元素如下定义：

最小的 5 个 Fibonacci 数 1, 2, 3, 5, 8 属于集合 F。
如果一个元素 x 属于 F，则 3x + 2、5x + 3 和 8x + 5 都属于集合 F。
其他元素都不属于 F。

请问，这个集合中的第 2020 小元素的值是多少？

//priority_queue<ll , vector<ll> , greater<ll> > mn; 小根堆 小到大 
//priority_queue<ll , vector<ll> , less<ll> > mx; 大根堆 大到小
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
typedef long long LL;
priority_queue<LL, vector<LL>, greater<LL>> q;
unordered_map<LL,bool> m;
int a[2040], idx;
int main()
{
    int cnt = 0;
    q.push(1); m[1] = true;
    q.push(2); m[2] = true;
    q.push(3); m[3] = true;
    q.push(5); m[5] = true;
    q.push(8); m[8] = true;
    while(!q.empty()){
        cnt++;
        LL x = q.top();
        q.pop();
        if(cnt == 2020){
            cout<<x<<endl;
            break;
        }
        LL w[] = {3 * x + 2, 5 * x + 3, 8 * x + 5};
        for(int i=0; i<3; i++){
            if(!m[w[i]]){
                m[w[i]] = true;
                q.push(w[i]);
            }
        }

    }
    return 0;
}

1246. 等差数列

由于给出的数列一定是等差数列，所以两两元素之间必定是差d的倍数，要得到完整的序列最短且包含原给出的序列，就要让公差d尽可能大，即d最大的情况是d是给定元素之间两两差值的最大公约数。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N], ans, n; 

int gcd(int a, int b){
    return b ? gcd(b, a%b) : a;
}

int main()
{
    cin>>n;
    for(int i=0; i<n; i++) cin>>a[i];
    sort(a, a+n);
    int t = 0;
    for(int i=0; i+1<n ;i++) t = gcd(t, a[i+1] - a[i]);
    if(!t) cout<<n<<endl;
    else cout<<(a[n-1] - a[0]) / t + 1<<endl;
    return 0;
}

#include <iostream>
using namespace std;
const int N = 10;
int e[N][N], p[N], ans;
bool st[N];//true表示第i盏灯亮 

void init(){
    e[1][2] = e[1][6] = 1;
    e[2][1] = e[2][7] = e[2][3] = 1;
    e[3][2] = e[3][7] = e[3][4] = 1;
    e[4][3] = e[4][5] = 1;
    e[5][4] = e[5][7] = e[5][6] = 1;
    e[6][1] = e[6][7] = e[6][5] = 1;
    e[7][2] = e[7][3] = e[7][5] = e[7][6] = 1;
}

int find(int x){
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void dfs(int n){
    if(n>7){
        for(int i=1; i<=7; i++) p[i] = i;
        for(int i=1; i<=7; i++)//将所有亮的灯做连通合并 
            for(int j=1; j<=7; j++)
                if(e[i][j] == 1 && st[i] && st[j])
                    p[find(i)] = find(j);
        int cnt = 0;
        for(int i=1; i<=7; i++){//遍历所有亮着的灯是否只与同一个灯连通 
            if(st[i] && p[i] == i) 
                cnt++;
        }
        if(cnt == 1) ans++;
        return;
    }
    st[n] = true;
    dfs(n+1);
    st[n] = false;
    dfs(n+1);
}

int main()
{
    init();
    dfs(1);
    cout<<ans<<endl;
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;

int n, m, a[N], ans=N, sum[N];//sum[i]第i辆车 

bool cmp(int a, int b){
    return a>b;
}

void dfs(int x, int k){//a[x]表示第x个小猫的重量，k表示第k辆车
    if(k >= ans) return;
    if(x == n){
        ans = k;
        return;
    }
    for(int i=0; i<k; i++){//判断a[x]能放进前k-1辆车的哪一台车 
        if(a[x] + sum[i] <= m ){
            sum[i] += a[x];
            dfs(x+1, k);
            sum[i] -= a[x];//恢复现场
        }
    }
    //新加一台车放进去
    sum[k] = a[x];
    dfs(x+1, k+1);
    sum[k] = 0;//恢复现场
} 

int main()
{
    cin>>n>>m;
    for(int i=0; i<n; i++) cin>>a[i];
    sort(a, a+n, cmp);
    dfs(0, 0);
    cout<<ans;
    return 0;
}

165. 小猫爬山

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;

int n, m, a[N], ans=N, sum[N];//sum[i]第i辆车 

bool cmp(int a, int b){
    return a>b;
}

void dfs(int x, int k){//a[x]表示第x个小猫的重量，k表示第k辆车
    if(k >= ans) return;
    if(x == n){
        ans = k;
        return;
    }
    for(int i=0; i<k; i++){//判断a[x]能放进前k-1辆车的哪一台车 
        if(a[x] + sum[i] <= m ){
            sum[i] += a[x];
            dfs(x+1, k);
            sum[i] -= a[x];//恢复现场
        }
    }
    //新加一台车放进去
    sum[k] = a[x];
    dfs(x+1, k+1);
    sum[k] = 0;//恢复现场
} 

int main()
{
    cin>>n>>m;
    for(int i=0; i<n; i++) cin>>a[i];
    sort(a, a+n, cmp);
    dfs(0, 0);
    cout<<ans;
    return 0;
}

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

const int N = 10, M = 10; 
int a[N][M], n, m, k, dx[] = {-1,0,1,0}, dy[] = {0,-1,0,1};// 上左下右 
unordered_set<int> s;

void dfs(int i, int j, int d, int num){
    if(d == k){
        s.insert(num);
        return;
    }
    for(int k=0; k<4; k++){
        int x = i + dx[k], y = j + dy[k];
        if(x >= 0 && x < n && y >= 0 && y < m)
            dfs(x, y, d+1, num*10+a[x][y]);
    }
}

int main()
{
    cin>>n>>m>>k;
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            cin>>a[i][j];

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            dfs(i, j, 0, a[i][j]);
        }
    }
    cout<<s.size();
    return 0;
}