F 整除序列
有一个序列，序列的第一个数是 n，后面的每个数是前一个数整除 2，出这个序列中值为正数的项。
样例
输入
20
输出
20 10 5 2 1
数据范围
对于$ 80% $的评测用例，$1 ≤ n ≤ 10^9$。
对于所有评测用例，$1 ≤ n ≤ 10^{18}$。
思路
暴力就可以了，注意数据范围，要开long long类型
C++ 代码
#include<iostream>
using namespace std;
int main(){
long long int n;
cin>>n;
while(n!=0){
cout<<n<<" ";
n/=2;
}
return 0;
}
G 解码
小明有一串很长的英文字母，可能包含大写和小写。
在这串字母中，有很多连续的是重复的。小明想了一个办法将这串字达得更短：将连续的几个相同字母写成字母+出现次数的形式。
例如，连续的 5 个 a，即 aaaaa，小明可以简写成a5（也可能简写aa3a等）。
对于这个例子：HHHellllloo，小明可以简写成 H3el5o2。小明不会将连续的超过 9 个相同的字符写成简写的形式。
现在给出简写后的字符串，请帮助小明还原成原来的串。
样例
输入
H3el5o2
输出
HHHellllloo
数据范围
对于所有评测用例，字符串由大小写英文字母和数字组成，长度不100。
请注意原来的串长度可能超过 100。
思路
直接遍历就可以了
C++ 代码
#include<iostream>
#include<string>
using namespace std;
string s,res="";
int main(){
cin>>s;
for(int i=0;s[i];i++){
int idx=s[i]-'0';
if(idx>0&&idx<=9){
for(int j=1;j<idx;j++){
res+=s[i-1];
}
}
else res+=s[i];
}
cout<<res<<endl;
return 0;
}
H 走方格
在平面上有一些二维的点阵。
这些点的编号就像二维数组的编号一样，从上到下依次为第1至第从左到右依次为第1至第m列，每一个点可以用行号和列号来表示。
现在有个人站在第 1 行第 1 列，要走到第 n 行第 m 列。只能向右或者下走。
注意，如果行号和列数都是偶数，d不能走入这一格中。问有多少种方案。
样例
输入一行包含两个整数 n, m。
输入：
3 4
6 6
输出
2
0
数据范围
$1 ≤ n ≤ 30, 1 ≤ m ≤ 30$
思路
数据范围比较小，所以可以使用DFS做，直接背模板就可以。
也可以使用线性DP去做
C++ 代码
DFS
#include<iostream>
using namespace std;
int n,m,res;
int dx[2]={1,0};
int dy[2]={0,1};
void dfs(int x,int y){
if(x==n&&y==m){
res++;
return;
}
for(int i=0;i<2;i++){
int ix=x+dx[i];
int iy=y+dy[i];
if(ix>n||iy>m||(ix%2==0&&iy%2==0)) continue;
dfs(ix,iy);
}
}
int main(){
cin>>n>>m;
dfs(1,1);
cout<<res;
}
线性DP,类似于AcWing 898题数字三角形
#include<iostream>
using namespace std;
const int N=35;
int n,m,f[N][N];
int main(){
cin>>n>>m;
f[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;
f[i][j]+=f[i-1][j]+f[i][j-1];
}
}
cout<<f[n][m];
}
I 整数拼接
给定义个长度为 n 的数组 $A_1, A_2, · · · , A_n$。你可以从中选出两个数 $A_i,A_j$ (i 不等于 j)，然后将 $A_i$ 和 $A_j$ 一前一后拼成一个新的整数。例如 12 和345可以拼成 12345 或 34512。注意交换 $A_i$ 和 $A_j$ 的顺序总是被视为 2 种拼法，即便是 $A_i = A_j$ 时。请你计算有多少种拼法满足拼出的整数是 K 的倍数。
第一行包含 2 个整数 n 和 K。
第二行包含 n 个整数$ A_1, A_2, · · · , A_n$。
样例
输入
4 2
1 2 3 4
输出
6
数据范围
对于 30% 的评测用例，$1 ≤ n ≤ 1000, 1 ≤ K ≤ 20, 1 ≤ A_i ≤ 10^4$。
对于所有评测用例，$1 ≤ n ≤ 10^5，1 ≤ K ≤ 10^5，1 ≤ A_i ≤ 10^9$
思路
暴力的话双重循环，时间复杂度$O(n^2)$当n取到$(10^5)$就超时了,不过应该能拿30%的分。
可以一些数学知识对数据做一些预处理，牺牲一些空间来降低时间复杂度
C++ 代码
//回去写
网络分析
小明正在做一个网络实验。
他设置了 n 台电脑，称为节点，用于收发和存储数据。
初始时，所有节点都是独立的，不存在任何连接。
小明可以通过网线将两个节点连接起来，连接后两个节点就可以互相了。两个节点如果存在网线连接，称为相邻。
小明有时会测试当时的网络，他会在某个节点发送一条信息，信息会到每个相邻的节点，之后这些节点又会转发到自己相邻的节点，直到所有或间接相邻的节点都收到了信息。
所有发送和接收的节点都会将信息存储一条信息只存储一次。
给出小明连接和测试的过程，请计算出每个节点存储信息的大小。
输入格式
输入的第一行包含两个整数 n, m，分别表示节点数量和操作数量。节1 至 n 编号。
接下来 m 行，每行三个整数，表示一个操作。
如果操作为 1 a b，表示将节点 a 和节点 b 通过网线连接起来。当 时，表示连接了一个自环，对网络没有实质影响。
如果操作为 2 p t，表示在节点 p 上发送一条大小为 t 的信息。
输出格式
输出一行，包含 n 个整数，相邻整数之间用一个空格分割，依次表示完上述操作后节点 1 至节点 n 上存储信息的大小。
样例
输入
4 8
1 1 2
2 1 10
2 3 5
1 4 1
2 2 2
1 1 2
1 2 4
2 2 1
输出
13 13 5 3
数据范围
对于 30% 的评测用例，1 ≤ n ≤ 20，1 ≤ m ≤ 100。
对于 50% 的评测用例，1 ≤ n ≤ 100，1 ≤ m ≤ 1000。
对于 70% 的评测用例，1 ≤ n ≤ 1000，1 ≤ m ≤ 10000。
对于所有评测用例，1 ≤ n ≤ 10000，1 ≤ m ≤ 100000，1 ≤ t ≤ 100。
思路
刚开始直接想到用并查集直接去做，但是每次发消息的时候都需要遍历所有的结点，时间复杂度$O(mn)$最多会达到$10^{10}$会超时，但是大概可以过$70%$的用例
C++ 代码
#include<iostream>
using namespace std;
const int N=10010,M=1e5+10;
int fa[N],e[N],n,m;
void init(){
for(int i=0;i<N;i++){
fa[i]=i;
}
}
int find(int a){
if(fa[a]!=a) fa[a]=find(fa[a]);
return fa[a];
}
void merge(int a,int b){
fa[find(a)]=find(b);
}
//以上三个都是并查集的模板
int main(){
cin>>n>>m;
init();
for(int i=0;i<m;i++){
int op,a,b;
cin>>op>>a>>b;
if(op==1){
merge(a,b);
}
if(op==2){
for(int i=1;i<=n;i++){
if(find(i)==find(a)){
e[i]+=b;
}
}
}
}
for(int i=1;i<=n;i++){
cout<<e[i]<<" ";
}
return 0;
}
