整除序列
题目描述：
有一个序列，序列的第一个数是 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[j]作为b的情况，假设,则我们需要求 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],,表示乘以 %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;
}
