整除序列

题目描述：

有一个序列，序列的第一个数是 n，后面的每个数是前一个数整除 2，请输出这个序列中值为正数的项

思路：

模拟就行

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    ll n; cin >> n;
    while(n){
        cout << n << ' ';
        n /= 2;
    }
    cout << endl;
    return 0;
}

解码

题目描述：

给出缩写后的字符串，让你还原回去，缩写的方式是将一段长度小于10的相同的字符串缩写成一个字符+一个数字的形式

思路：

模拟就行

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); ++i){
        if(s[i] >= '0' && s[i] <= '9'){
            int p = s[i] - '1';
            while(p>0)cout<<s[i-1], --p;
        }
        else cout<<s[i];
    }
    return 0;
}

走方格

题目描述：

二维矩阵，你在(1, 1)问到(n, m)的路线的数量，其中不能走横纵坐标都是偶数的点

思路：

最简单的dp计数

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
int tr[MAX];
int dp[50][50];

void work(){
    cin >> n >> m;
    dp[1][1] = 1;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(i % 2 == 0 && j % 2 == 0)continue;
            dp[i][j] += dp[i - 1][j] + dp[i][j - 1];
        }
    }
    cout << dp[n][m] << endl;
}


int main(){
    io;
    work();
    return 0;
}

整数拼接

题目描述：

给定长度为n的数组a[i]，你可以从中选择出两个数a[i], a[j](i != j)，将其一前一后拼在一起形成一个新的数字，例如：12和345可以拼接出12345或者34512，问存在多少种拼接方法，使的拼接出来的数是k的倍数

思路：

很有意思的一个题

我们将在前面的数字叫做a, 将后面的数字叫做b

拼接得到的数字可以被拆成两部分：$a*10^{log_{10}{b}+1}$和$b$两部分

我们先考虑每个数a[j]作为b的情况，假设 $p=10^{log_{10}{b}+1}$,则我们需要求1到j-1中出现的数a[i]，能满足(a[i]*p) % k + a[j] % k) %k = 0,也就是(a[i]*p) % k = k - a[j] % k

所以我们可以开一个数组tr[pp][x],$pp={log_{10}{b}+1}$,表示乘以 $x*10^{pp}$%k后等于x的数量,对于每个数x，当她作为拼接的后半部分数字的情况，答案是tr[pp][(k-tr[i]%k)%k]

注意要判断不能用同一个数，自己和自己能结合的情况就是：(tr[i]+tr[i]*pp)%k=0

特别特别坑的一个点是，极限情况下使用pow函数和数字相乘会爆longlong，用快速幂就行

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
ll n, m, k;
ll tr[MAX];
ll num[15][MAX];

ll q_pow(ll a, ll b, ll mod){
    ll ans = 1;
    while(b > 0){
        if(b & 1)ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}


inline ll lg(ll x){
    ll num = 0;
    while (x) {
        ++num;x /= 10;
    }
    return num;
}

void work(){
    cin >> n >> k;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    for(int i = 1; i <= n; ++i){
        ll p = 1;
        for(int j = 0; j <= 10; ++j){
            ++num[j][(tr[i] * p) % k];
            p = (p * 10) % k;
        }
    }
    ll ans = 0;
    for(int i = 1; i <= n; ++i){
        ans += num[lg(tr[i])][(k - (tr[i]%k))%k];
        if((tr[i] + (tr[i] * q_pow(10, lg(tr[i]), k))%k)%k == 0)--ans;
    }
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}

网络分析

题目描述：

两种操作

• 1 x y，表示将x和y连接起来
• 2 x c，表示将与x在同一个连通块的点的权值+c

问最后每个点的权值是多少

思路：

带权并查集

tr[i]表示节点i的权值

对于权值修改，我们只需要修改根节点的权值，这样每个点的答案就是当前点到跟节点上路径的权值

如何进行路径压缩？

int getfa(int x){
 if(x == fa[x] || fa[fa[x]] == fa[x])return fa[x];//如果当前点就是根节点或者当前点的父亲节点就是根节点，就返回
 int root = getfa(fa[x]);
 tr[x] += tr[fa[x]];//先更新权值
 fa[x] = root;//再更新父节点
 return fa[x];
}

如何合并？

int xx = getfa(x);
int yy = getfa(y);
if(xx == yy)continue;//如果在同一个连通块内就不用管
tr[xx] -= tr[yy];//消除新的根节点yy的权值的影响
fa[xx] = yy;//更新根节点

答案怎么输出：

for(int i = 1; i <= n; ++i){
 if(i == getfa(i))cout << tr[i] << ' ';//如果自己就是根节点，就直接输出
 else cout << tr[getfa(i)] + tr[i] << ' ';//否则，经过路径压缩后，一定是直接连接在根节点上面，所以答案是两部分，加上就行
}

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
int tr[MAX];
int fa[MAX];

int getfa(int x){
    if(x == fa[x] || fa[fa[x]] == fa[x])return fa[x];
    int root = getfa(fa[x]);
    tr[x] += tr[fa[x]];
    fa[x] = root;
    return fa[x];
}

void work(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)fa[i] = i;
    for(int i = 1, op, x, y; i <= m; ++i){
        cin >> op >> x >> y;
        if(op == 1){
            int xx = getfa(x);
            int yy = getfa(y);
            if(xx == yy)continue;
            tr[xx] -= tr[yy];
            fa[xx] = yy;
        }
        else{
            int xx = getfa(x);
            tr[xx] += y;
        }
    }
    for(int i = 1; i <= n; ++i){
        if(i == getfa(i))cout << tr[i] << ' ';
        else cout << tr[i] + tr[getfa(i)] << ' ';
    }
    cout << endl;
}


int main(){
    io;
    work();
    return 0;
}

超级胶水

题目描述：

n颗石子，按顺序排成一排

每个石子都有自己的重量，相邻两个石子粘起来的花费是两个石子的重量的乘积，每次只能粘相邻的两个石子，问将所有的石子粘起来的最小花费是多少

思路：

假设当前有三个石子，重量是a, b, c

粘1, 2后花费：a*b

再粘剩下的两个，花费是(a+b)*c

总花费是：ab + ac + bc

不难发现，无论粘贴的顺序如何，结果是不变的

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
ll ans, sum;
ll tr[MAX];

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    sum = tr[1];
    for(int i = 2; i <= n; ++i){
        ans += sum * tr[i];
        sum += tr[i];
    }
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}