前言：
不知道为啥，今天好累。。。。\(But...\)今天完成了一件大事：我终于把我写的草稿文变成电子版的了~（虽然被说是小学生文笔了，但是还是很开心）
link 快来提建议呀~~（但是不建议你们骂我，真的会哭的【呜哇哇】）
\(T1：\)[arc084_b]Small Multiple
思路：
先来考虑最暴力的想法：枚举每一个\(K\)的倍数并求和。很显然，这会直接\(T\)飞。那么我们来考虑如何简化一下这个过程呢。我们不妨考虑一下求和过程：先看个位，1的位和为1,2的位和为2，以此类推逐渐+1.再来考虑十位，无非就是个位\(×10\)。所以总结一下，我们可以整理出两种状态：\(×10\)和\(+1\).注意，\(×10\)的话它的位和是不变的。然后有人发出了疑问，需不需要开\(long \ \ long\)甚至写高精，答案是否定的。思考一下，我们要求的是\(K\)的倍数，所以我们只需要对\(K\)进行取模就好了。最后，我们采取双端队列，把乘十放在前面，加一放在后面（因为乘十的位和不变，答案更优）。这题就这样结束了~~
代码：
#include<iostream>
#include<queue>
using namespace std;
struct node{int num,sum;};
int k,vis[100005];deque<node> q;
int main(){ios::sync_with_stdio(false);cin>>k;q.push_front({1,1});vis[1]=1;//塞入初始值 while(!q.empty()){int num=q.front().num,sum=q.front().sum;if(num==0){//有符合要求的答案 cout<<sum<<'\n';return 0;}if(!vis[10*num%k]){//如果不标记的话会有死循环（可以手模一下） q.push_front({10*num%k,sum});//乘十 vis[10*num%k]=1;//防止死循环 }if(!vis[num+1]) q.push_front({num+1,sum+1});//加一 }return 0;
}
\(T2：\) AT_abc216_g [ABC216G] 01Sequence
思路：
有个小知识点之前没学过：差分约束（其实现在还没完全学会，明天再巩固一下叭~）这道题可以用前缀和来统计\(1\)的个数，显然有式子\(s_i-s_{i-1}≥0,s_{i-1}-s_{i}≤-1\)。为了防止下标出现负数，我们把下标统一 \(+1\)。最后输出所有 \(dis_i−dis_{i-1}\)就行。因为这道题卡\(SPFA\)，所以我们考虑用\(dij\)，但是\(dij\)的边权不能为负数。所以需要我们转换一下思维，把统计\(1\)的个数改为统计\(0\)的个数。由此，式子变成了\(s_{b_i}−s_{a_i-1}≤b_{i}−a_i+1−c_i,s_i−s_{i-1}≤1,s_{i-1}−s_{i}≤0\)，由于解不等式同小取小原则，所以改成统计 \(0\) 之后要求最短路，最后输出方案的时候把答案取反就行了。
代码：
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#define pi pair<int,int>
using namespace std;
const int N=2e5+5;
int m,n,u,v,w,dis[N];bool vis[N];
vector<pi> C[N];
priority_queue<pi,vector<pi>,greater<pi>> q;
int main(){ios::sync_with_stdio(false);cin>>n>>m;for(int i=1;i<=m;i++){cin>>u>>v>>w;C[u].push_back({v-u+1-w,v+1});//建边 }for(int i=0;i<=n;i++) C[i].push_back({1,i+1}),C[i+1].push_back({0,i});//建边 memset(dis,0x3f,sizeof(dis));q.push({0,0});dis[0]=0;//初始化 while(!q.empty()){int u=q.top().second;q.pop();if(vis[u]) continue;vis[u]=1;for(unsigned int i=0;i<C[u].size();i++){if(dis[C[u][i].second]>dis[u]+C[u][i].first){dis[C[u][i].second]=dis[u]+C[u][i].first;q.push({dis[C[u][i].second],C[u][i].second});}//最短路 }}for(int i=2;i<=n+1;i++) cout<<!(dis[i]-dis[i-1])<<" ";//取反输出 return 0;//完结撒花~~
}