趁着早上量子力学的课，把这台Vultr服务器重装了系统。
距上次重装只过了1年有余，然而现在看其上部署的服务已经觉得是一坨屎山了。换个角度想，没准这说明这一年以来本人学到了不少服务器知识（
总之这最后的一台Debian服务器也变成了Ubuntu 24.04LTS，还顺手重写了初始化脚本。之后服务器的OS估计也尽量使用Ubuntu了。唯一担心的是听说Ubuntu的性能消耗大于Debian，这台1vCPU，1GB RAM的小VPS不一定撑得住。但目前似乎没什么大问题
不知道下一次再次感叹这座屎山是什么时候，希望不会太久
这是这个网站建立的第四年！
话虽如此，上一篇文章也是三年前的东西了。现在看来内容也不过尔尔。如果真的有人在读这篇文章的话，你大可以期待之后的内容会比现在更加精彩。
如果今后的文章篇幅较短，可能会用中日双语。第二外语选中文的读者们，或许可以拿来做学习的参考。
那么，今后还请多关照。
このサイトは四年目に入りました！
とは言え、前回の文章も3年前のものだし、今から見れば内容もクソみたいなものしかない。もし本当に誰かがこの文章を読んでいたら、その後の内容が今よりも素晴らしいと期待できるはず。
今後の文章の本文が短い場合、中国語と日本語両方載せることもあるので、 中国語を第二外国語として選んだ人には、勉強の参考になるかもしれない。
それでは、今後もよろしくお願いします。
今日（19.9.8）与一友人讨论“萌战”话题的时候，我用圈地自萌一词形容所谓“角色萌战应援”群体。细想开，“圈地自萌”有很多值得说道的地方。
在此声明，由于汉语的多意性，“圈地自萌”有多重理解。在我的观念中其意思是“猪圈中的猪觉得自己很萌”，是一个贬义词。
这类所谓“萌战应援”，通常只是在萌战期间统一投票、甚至购买票数，让自己喜爱的角色获得高名次，来展现自己的“厨力”。而事实上萌战的重点根本不仅仅是投票，而是关于动画角色的交流、支援，以及相关文艺作品的创作。把萌战看做投票无疑是管中窥豹。单纯的为了一个空头衔而投入大量时间精力，只是助长了资本对于角色的消费，对个人、对角色、以至对于整个ACGN圈子而言无疑是毫无价值的。
所谓价值，便是事物被创造的心血。我欣赏论坛社区上对角色或作品的评析，也喜爱视频网站上精美的AMV与手书。它们的创造者们无一不在为角色的丰满、作品的精美而添砖加瓦。它们又像催化剂一样，能激发读者们的思考甚至更多的创造物。正因如此，作品得以宏大、角色得以立体。这就是价值。而上文所述的“圈地自萌”，无疑是创造的对立面，是消费主义的陷阱。
既然如此，那么为什么会有人愿意参加这一类的行动呢？自我的标签化可能是其主因。将自己归类为某一个标签，便可以自豪的向外界宣布：“我是加○惠的粉丝”，“我是左圈（juan）人”。是为了快速寻找到认同感与存在感。与相同标签的人，便获得了一种归属感，而这份归属感或许是进行“角色萌战应援”等无义行为的原因。
但当你找到了这种归属感之后呢？当你背负着一堆标签和人交流，就并不是看某个观点有何见解怎么样，而是看发表观点的人本身的文化、喜好等身份背景。一个人的身份便决定了他的观点，从而实质性的对话烟消云散。社会身份的认同，取代了真正的、可能比较艰难的讨论、思考的过程。便没有了新的创造，没有了新的价值。
不得不提一个概念“鄙视链”。鄙视链现象客观存在，与其说是鄙视链，其实更接近一个拓扑图。在鄙视链上端的人往往会看不起鄙视链下端的人。这并不是一件坏事，正因为鄙视链的存在，很多人产生了向上爬的欲望，从而得到了自我的提升。而上文所述的自我标签化与身份认同，也是一种对于鄙视链的逃避。当一个人沉浸在小圈子中，长久便会坐井观天，不愿接受新事物、不愿学习新事物，以狭隘的价值观反过来嘲笑正在向上爬的人。这便是“圈地自萌”的另一个坏处，即自我麻醉。
说了这么多，仔细想想所谓“知乎er”等称号，不也是一种圈地自萌吗？
十月的《青春猪头少年不会梦见兔女郎学姐》（以下简称《青春猪头》）一开始我是不看好的。作为没看过原著的本人，看到这个标题第一反应无论如何也称不上有兴趣——大概率又是一部媚宅的作品罢。而到看完第13集后，却也不得不承认这是一部不错的轻改作品。
青春期的心理活动对于文艺作品而言无疑是个老生常谈的话题，对于受众主要为青少年的ACGN相关作品而言更是如此。这部作品通过想象了一种名为“青春期综合征”的现象来推动情节。这个所谓的综合征并不是传统意义上的，精神层面的所谓“中二病”，而是一种唯精神的，因为心理状态而影响到了现实物质世界的现象。这种映射与夸张在动画中很常见，典型的就例如“傲娇”，傲娇是对于爱恋而又耻于表达的一种腼腆，动画将其通过神态与语言的形式将其展露，这是一个非常典型的夸张，毕竟现实中可不会有红着脸说着“才…才不是为你准备的呢，别会错意了啊！”一遍时不时看你一眼的美少女。这种手法的优势在于能迅速将一个原本抽象的物体生动地向读者展现，正如本作所体现的那样。对于女主而言，便是从偶像活动中隐退，不希望与同学接触，以至于女主的存在不被任何人观测，甚至也就彻底从物理意义上消失了。而对于受到校园欺凌的男主妹妹，则是出现了失忆与对迈出家门的恐惧。
这部作品的刻画在我看来也较为细致，人物刻画的最大难题之一的“脸谱化”在这部作品中得到了一定程度上的解决，除了类似“机械降神”般的男主初恋，其余的人物也并不扁平。以女主为例，女主的设定如果归类也是属于上文提及的“傲娇”，但是作品中女主的表现较与传统的傲娇而言，则更加的去夸张化。女主的性格属性如果放到现实生活当中我想也不会觉得突兀。这种贴近现实的人物塑造也是本作的特点之一。虽然史密斯老师教导我们不要在虚拟作品中寻找真实感。这句话其实没错，虚构作品作为现实生话的一个补完，本身的目的就是为了读者“爽”，从这点上，现实感似乎是与虚拟背道而驰的。但是从另一个角度而言，真实感在虚构作品中作用就是让我们死肥宅们更好的带入，观众们在观看本片时或许会将作品的人物映射到现实中，自然也会有所感悟。
对于一部轻改作品而言，《青春猪头》十三集的篇幅不免显得有些拘束。知乎上有人笑称其是“3集相当于1季”。这点在剧情前段的“循环”剧情中体现的尤为明显——特别是和《凉宫春日》的漫无止境的八月比起来。暂且不论《凉宫》8集循环的优劣，至少在一集以内的篇幅里，作品中人物的心境是完全无法让观众感同身受的。我不是很清楚动画制作方选择制作季番的目的是什么。对于一部原作良好，又有相当潜在受众的作品，做24集完全不是问题。即使是资金问题，分成两季也是可以接受的。另外，这是原作的锅，片中出现了大量我们看来是“强行解释”的“量子力学”的相关内容，这些在我看来只是画蛇添足。
我们常说小说的剧情来源于人事物间的矛盾与冲突，这个看法放之所有文艺作品而皆准。这部作品作为群像故事，在这方面无疑是有先天优势的。而群像小说的弱势——人物刻画，本作也通过加大真实感规避了这个问题。抛开强行科学的部分不谈，这部作品的水准仍是良好接近优秀的。若是来评分8.5分我认为也不为过。
斯波题，若四条边界上有1，直接输出2，否则输出4。好玩的是我还成功误导了某位同学，使他误以为是DFS（笑）。
#include<bits/stdc++.h>
#define N 101
using namespace std;
int n,m;
int main(){
freopen("table.in","r",stdin);
freopen("table.out","w",stdout);
cin>>n>>m;
int flag=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int x;
cin>>x;
if (x)
if (i==1||i==n||j==1||j==m) flag=1;
}
}
if (flag) cout<<2; else cout<<4;
return 0;
}
考场上愣是没看出来DP，惨遭20。其实正解也不难，见下。
将连续的相同字符压缩为同一个，
例如aabbaacc即为abac
我们可以发现，字母的顺序是不会换的，比如abac就不可能变换为abca。
所以就可以用类似背包的思想，f[i][x][y][z]代表最后一个选的字符是原串第i位，用了x个a y个b z个c的答案。
方程就是
f[nex[i][0]][a+1][b][c]=(f[nex[i][0]][a+1][b][c]+f[i][a][b][c]);
f[nex[i][1]][a][b+1][c]=(f[nex[i][1]][a][b+1][c]+f[i][a][b][c]);
f[nex[i][2]][a][b][c+1]=(f[nex[i][2]][a][b][c+1]+f[i][a][b][c]);
其中next[i][0..2]为预处理原串字符i后面（包括自身）最近的’a”b”c’的位置。
代码如下
#include<bits/stdc++.h>
#define ll long long
#define mod 51123987
using namespace std;
int n,nex[210][3],stand;
ll f[155][55][55][55],ans;
char c[155];
bool check(int a,int b,int c){
return (a+b+c==n)&&(fabs(a-b)<=1)&&(fabs(c-b)<=1)&&(fabs(a-c)<=1);
}
int main(){
freopen("balance.in", "r", stdin);
freopen("balance.out", "w", stdout);
cin>>n;
cin>>c;
nex[n+1][0]=nex[n+1][1]=nex[n+1][2]=n+1;
for(int i=n;i>=1;i--){
nex[i][0]=nex[i+1][0],nex[i][1]=nex[i+1][1],nex[i][2]=nex[i+1][2];
nex[i][c[i-1]-'a']=i;
}
ans=0,stand=(n+2)/3,f[1][0][0][0]=1;
for(int i=1;i<=n;i++)
for(int a=0;a<=stand;a++)
for(int b=0;b<=stand;b++)
for(int c=0;c<=stand;c++){
if(check(a,b,c)){
ans+=f[i][a][b][c];
}
if(nex[i][0]<=n) f[nex[i][0]][a+1][b][c]=(f[nex[i][0]][a+1][b][c]+f[i][a][b][c])%mod;
if(nex[i][1]<=n) f[nex[i][1]][a][b+1][c]=(f[nex[i][1]][a][b+1][c]+f[i][a][b][c])%mod;
if(nex[i][2]<=n) f[nex[i][2]][a][b][c+1]=(f[nex[i][2]][a][b][c+1]+f[i][a][b][c])%mod;
}
cout<<ans%mod<<endl;
return 0;
}
如果熟悉二分图和各种树上操作的话应该不难（但是我不会）。
思路很明确：给一张无向图，求删掉哪几条边可以变成二分图；
定义一个环为奇环当且仅当环包含的边数为奇数，偶环同理。
我们会发现，
如果没有奇环，那么任何边都可以删；
如果只有一个奇环，那么奇环上的边都可以被删；
如果多于1个，必须选在所有奇环且不在偶环上的点；
那么怎么找奇环呢？
这里要说到DFS树的两个特点，第一，树上的边要么构成一条链，要么是返祖边。第二，树上的LCA就是深度较浅的点。
这里的返祖边就是我们要找的环了。考虑到树上差分，它应该在两个端点+1，LCA-2。根据上面的第二点，我们将深度较浅的点+1-2即可。
统计tag==n的点，输出他的father即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define ri register int
#define il inline
#define fi first
#define se second
#define mp make_pair
#define pi pair<int,int>
#define mem0(x) memset((x),0,sizeof (x))
#define mem1(x) memset((x),0x3f,sizeof (x))
#define gc getchar
#define pb push_back
template<class T>void in(T &x){
x = 0; bool f = 0; char c = gc();
while (c < '0' || c > '9') {if (c == '-') f = 1; c = gc();}
while ('0' <= c && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = gc();}
if (f) x = -x;
}
#undef gc
void out(int x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) out(x / 10);
putchar(x % 10 + '0');
}
#define N 10010
#define M N<<2
int n, m;
int v[M], u[M], nx[M], k[M];
int cnt = 1, head[N];
il void add(int uu, int vv) {
u[++cnt] = uu, v[cnt] = vv, nx[cnt] = head[uu];
head[uu] = cnt;
k[cnt] = (cnt >> 1);
}
int dep[N];
bool vis[N];
int tag[N];
int zt;
vector<int>ans;
int lst;
void dfs(int x, int f, int d) {
//printf("V %d\n",x);
dep[x] = d;
vis[x] = 1;
for (ri i = head[x]; i; i = nx[i]) {
if (i == f) continue;
if (!vis[v[i]]) {
dfs(v[i], i ^ 1, d + 1);
}
else {
if (dep[v[i]] < dep[x]) continue;
if ((dep[v[i]] - dep[x] + 1) & 1) {
tag[x]--; // in fact +1 -2
tag[v[i]]++;
zt++;
lst=k[i];
}
else {
tag[x]++;
tag[v[i]]--;
}
}
}
}
int dfs2(int x, int f) {
vis[x] = 1;
int res = tag[x];
for (ri i = head[x]; i; i = nx[i]) {
if (vis[v[i]]) continue;
res += dfs2(v[i], i);
}
if (res == zt) ans.pb(k[f]);
//printf("T %d %d %d\n",x,res,tag[x]);
return res;
}
signed main() {
in(n), in(m);
for (ri i = 1, a, b; i <= m; ++i) {
in(a), in(b);
add(a, b);
add(b, a);
}
for (ri i = 1; i <= n; ++i) {
if (!vis[i]) dfs(i, 0, 0);
}
if (zt == 0) {
//cout << "A";
printf("%d\n", m);
for (ri i = 1; i <= m; ++i) printf("%d ", i);
return 0;
}
if(zt==1) ans.pb(lst);
//cout<<zt;
mem0(vis);
for (ri i = 1; i <= n; ++i) {
if (!vis[i]) dfs2(i, 0);
}
sort(ans.begin(), ans.end());
printf("%d\n", ans.size());
for (ri i = 0; i < ans.size(); ++i) {
printf("%d ", ans[i]);
}
return 0;
}
二分即可
#include<bits/stdc++.h>
using namespace std;
int n,m,d,l,r,mid,ans,a[100000];
bool judge(int x){
int tot=0,i=0,now=0;
while (i<n+1) {
i++;
if(a[i]-a[now]<x) tot++;
else now=i;
}
return tot<=m;
}
int main(){
freopen("stone.in","r",stdin);
freopen("stone.out","w",stdout);
cin>>d>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
a[n+1]=d,l=1,r=d;
while(l<=r){
mid=(l+r)/2;
if (judge(mid)){
ans=mid;
l=mid+1;
}
else r=mid-1;
}
cout<<ans;
return 0;
}
DP。我觉得和背包的思路挺像的一道题。用f1[i][j][k]表示两串分别到a[i]，b[j]，且a[i]必须使用时，用了k个子串的方案数。f2[i][j][k]表示无论用不用当前字符(A[i])时的方案数总和。那么转移方程就显而易见了：
f1[i][j][k]=f1[i-1][j-1][k-1]+f2[i-1][j-1][k]
f2[i][j][k]=f2[i][j][k]+f[i][j][k]
我们发现i这个维度是可以滚动的，于是就节省了一维空间
#include<bits/stdc++.h>
using namespace std;
int mod=1000000007;
char a[1001],b[201];
int n,m,k1,y,ans,f1[1001][200],f2[201][201];
int main(){
//freopen("substring.in","r",stdin);
//freopen("substring.out","w",stdout);
cin>>n>>m>>k1;
cin>>a>>b;
f1[0][0]=f2[0][0]=1;
for (int i=1; i<=n; i++)
for (int j=m; j>=1; j--)
for (int k=1; k<=k1; k++)
{
if (a[i-1]!=b[j-1]) {f1[j][k]=0; continue;}
f1[j][k]=(f1[j-1][k]%mod+f2[j-1][k-1]%mod)%mod;
f2[j][k]=(f2[j][k]%mod+f1[j][k]%mod)%mod;
}
printf("%d",f2[m][k1]);
return 0;
}
先Tarjan求m对点的lca，然后二分答案，把所有大于二分的答案的路径记录，判断有没有一条边被所有大于二分的答案的路径所重复，如果有，那么这条边必须大于等于最大的路径减二分的答案，如果上述两个条件都符合那么这个二分的答案就是合法的，细节参考代码。如果TLE加个快读即可。
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
typedef pair<int,int>PP;
struct node{
int to,dist,nu;
};
struct P{
int a,b,c;
};
int q[300002],n,m,hh[300002],ans[300002],anss[300002],lca[300002],h[300002],fa[300002],left,right,mid,f[300002];
P y[300002];
bool fl[300002];
vector<node>s[300002];
vector<PP>t[300002];
int find(int x){
if (fa[x]==x)return x;
else return fa[x]=find(fa[x]);
}
void dfs(int x,int tt){
anss[x]=tt;fa[x]=x;
for (int i=0;i<s[x].size();i++)
if (!fa[s[x][i].to])
{
h[s[x][i].to]=s[x][i].nu;
dfs(s[x][i].to,tt+s[x][i].dist);
fa[s[x][i].to]=find(x);
}
for (int i=0;i<t[x].size();i++)
if (fa[t[x][i].first])lca[t[x][i].second]=find(t[x][i].first);
}
void dfs(int x){//c++支持重载函数
for (int i=0;i<s[x].size();i++)
if (!fl[s[x][i].to])
{
fl[s[x][i].to]=1;
dfs(s[x][i].to);
f[h[x]]+=f[h[s[x][i].to]];
}
}
bool pd(int x){
int t=0,u,maxn=0;
memset(f,0,sizeof(f));
memset(fl,0,sizeof(fl));
for (int i=0;i<m;i++)
if (ans[i]>x){maxn=max(ans[i],maxn);q[t++]=i;}
if (!t)return true;
for (int i=0;i<t;i++)
{
u=q[i];
f[h[y[u].a]]++;//这条边+1
f[h[y[u].b]]++;//这条边+1
f[h[lca[u]]]-=2;//这条边-2，因为这条边虽然计算了两次，实际上一次都没有走到
}
dfs(1);
for (int i=1;i<n;i++)
if (f[i]==t && hh[i]>=maxn-x)return true;
return false;
}
int main()
{
scanf("%d%d",&n,&m);
int u,v,w,sum=0;
for (int i=1;i<n;i++)
{
scanf("%d%d%d",&u,&v,&w);sum+=w;
hh[i]=w;node g;
g.to=v;g.dist=w;g.nu=i;
s[u].push_back(g);
g.to=u;
s[v].push_back(g);
}
for (int i=0;i<m;i++)
{
scanf("%d%d",&y[i].a,&y[i].b);
t[y[i].a].push_back(PP(y[i].b,i));
t[y[i].b].push_back(PP(y[i].a,i));
}
dfs(1,0);
for (int i=0;i<m;i++)
ans[i]=anss[y[i].a]+anss[y[i].b]-2*anss[lca[i]];//a到b的距离等于1到a的距离+1到b的距离-1到lca(a,b)的距离
left=0;right=sum;
while(left<right)//二分答案
{
mid=(left+right)/2;
if (pd(mid))right=mid;
else left=mid+1;
}
printf("%d",right);
return 0;
}
按照题意模拟即可。
也是很水的一道题。有两种方法可以做。第一种是tarjan来求最小环，这个代码量略大。另外一种就是利用改版并查集，father数组存的是最远的祖先。具体实现看代码
#include<bits/stdc++.h>
using namespace std;
int f[200010],d[200010],n,minn,last;
int find(int x){
if (f[x]!=x){
int tmp=f[x];
f[x]=find(f[x]);
d[x]+=d[tmp];
}
return f[x];
}
int main(){
freopen("message.in","r",stdin);
freopen("message.out","w",stdout);
cin>>n;
for (int i=1;i<=n;i++) f[i]=i;
minn=0x7f7f7f7f;
for (int i=1;i<=n;i++) {
int t;
cin>>t;
int x=find(i),y=find(t);
if (x!=y) f[x]=y,d[i]=d[t]+1;
else minn=min(minn,d[i]+d[t]+1);
}
cout<<minn;
return 0;
}
这题挺有意思的，写完后发现会了很多斗地主技巧。首先一个显而易见的事实：有顺子时打顺子不一定是最优的，比如说我有一副 3 4 5 6 6 7 7 8 9 10，如果要打最长的顺子，这套牌要分三次才能打完。于是乎，我们只能暴力枚举了。另外其实还需要考虑其他的细节，但是这一题是随机数据，所以不加这些细节也能AC。如果要更高端的解法请移步这一题。
#include<bits/stdc++.h>
using namespace std;
int t,n,a[20],ans;
void dfs(int x){
if (x>ans) return;
int s1,s2,s3,s4;
s1=s2=s3=s4=0;
for(int i=1;i<=14;i++)//统计单牌与对子
{
if(a[i]==1) s1++;
if(a[i]==2) s2++;
}
for(int i=1;i<=14;i++)//四带的牌
if(a[i]==4)
{
s4++;
if(s1>=2) s1-=2;
else if(s2>=2) s2-=2;
else if(s2>=1) s2--;
}
for(int i=1;i<=14;i++)//三带的牌
if(a[i]==3)
{
s3++;
if(s1>=1) s1--;
else if(s2>=1) s2--;
}
ans=min(ans,x+s1+s2+s3+s4);//手中没牌，更新方案
//以下枚举顺子
int j;
for(int i=1;i<=8;i++){
for (j=i;j<=12;j++){
a[j]--;
if (a[j]<0) break;
if(j-i>=4) dfs(x+1);
}
if (j>=13) j--;
while (j>=i) a[j--]++;
}
for (int i=1;i<=10;i++){
for(j=i;i<=12;j++){
a[j]-=2;
if(a[j]<0) break;
if(j-i>=2) dfs(x+1);
}
if (j>=13) j--;
while (j>=i) a[j--]+=2;
}
for (int i=1;i<=11;i++){
for(j=i;i<=12;j++){
a[j]-=3;
if(a[j]<0) break;
if(j-i>=1) dfs(x+1);
}
if (j>=13) j--;
while (j>=i) a[j--]+=3;
}
}
int main(){
freopen("landlords.in","r",stdin);
freopen("landlords.out","w",stdout);
cin>>t>>n;
for(int i=1;i<=t;i++){
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
if (x==0) a[14]++;
if (x==1) a[12]++;
if (x==2) a[13]++;
if (x>=3) a[x-2]++;
}
ans=0x7f7f7f;
dfs(0);
cout<<ans<<endl;
}
return 0;
}
日狗了没有自动保存
题目找不到留言，我私发
给出一张有向图，可能有环，求最长链
求最长链我们可以用拓扑排序。但是拓扑排序不能有环，怎么处理呢？其实环就是一个强联通分量，所以我们可以用tarjan把强联通分量求出来，并且将其合并成一个点。这样问题就解决了。
#include<cstdio>
using namespace std;
const int N=1e6+1;
int tot,top,num,ans;
int first[N],next[N],en[N];
int first1[N],next1[N],en1[N];
int dfn[N],low[N],stack[N],MS[N],r[N];
int f[N],g[N],d[N],q[N],bel[N];
bool bz[N],vis[N];
inline int read()
{
int X=0,w=1; char ch=0;
while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
return X*w;
}
inline int max(int x,int y)
{
return x>y?x:y;
}
inline int min(int x,int y)
{
return x<y?x:y;
}
inline void insert(int x,int y)
{
next[++tot]=first[x];
first[x]=tot;
en[tot]=y;
}
inline void insert1(int x,int y)
{
next1[++tot]=first1[x];
first1[x]=tot;
en1[tot]=y;
d[y]++;
}
inline void tarjan(int x)
{
MS[MS[0]=1]=x;
while(MS[0])
{
if(!dfn[x=MS[MS[0]]])
{
dfn[x]=low[x]=++tot;
r[stack[++top]=x]=first[x];
bz[x]=vis[x]=true;
}
bool enter=false;
for(int i=r[x];i;i=next[i])
if(!vis[en[i]])
{
r[x]=next[i];
MS[++MS[0]]=en[i];
enter=true;
break;
}else
if(bz[en[i]]) low[x]=min(low[x],dfn[en[i]]);
if(enter) continue;
if(dfn[x]==low[x])
{
num++;
do
{
bel[stack[top]]=num;
bz[stack[top--]]=false;
}while(stack[top+1]!=x);
}
low[MS[--MS[0]]]=min(low[MS[MS[0]]],low[x]);
}
}
int main()
{
freopen("bomb.in","r",stdin);
freopen("bomb.out","w",stdout);
int n=read(),m=read();
for(int i=1;i<=m;i++)
{
int x=read(),y=read();
insert(x,y);
}
tot=0;
for(int i=1;i<=n;i++)
if(!vis[i]) tarjan(i);
tot=0;
for(int i=1;i<=n;i++)
{
g[bel[i]]++;
for(int j=first[i];j;j=next[j])
if(bel[i]^bel[en[j]]) insert1(bel[i],bel[en[j]]);
}
int l=0,r=0;
for(int i=1;i<=n;i++)
if(!d[i]) f[q[++r]=i]=g[i];
while(l<r)
{
int x=q[++l];
if(!first1[x]) ans=max(ans,f[x]);
for(int i=first1[x];i;i=next1[i])
{
f[en1[i]]=max(f[en1[i]],f[x]+g[en1[i]]);
if(!--d[en1[i]]) q[++r]=en1[i];
}
}
printf("%d\n",ans);
return 0;
}
有一坨房间，房间里可能有门或者钥匙。我们初始在房间x，要走到房间y。门通向另一个房间，但需要特定的数把钥匙才能开。求x到y的最短路径。
看上去没思路，于是就写个bfs，发现bfs可以过。
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
struct node
{
int dot,s,step;
node(){}
node(int x,int y,int z):dot(x),s(y),step(z){}
};
struct node1
{
int to,s;
node1(){}
node1(int x,int y):to(x),s(y){}
};
int n,m,k,a[5005];
bool b[5005][2048];
queue<node> p;
vector<node1> c[5005];
void bfs()
{
p.push(node(1,a[1],0));
while (!p.empty())
{
node u=p.front();
p.pop();
if (u.dot==n)
{
cout<<u.step;
return;
}
for (int i=0;i<c[u.dot].size();i++)
{
int v=c[u.dot][i].to;
if ((u.s&c[u.dot][i].s)==c[u.dot][i].s&&b[c[u.dot][i].to][u.s|a[v]]==0)
{
b[c[u.dot][i].to][u.s|a[v]]=1;
p.push(node(v,u.s|a[v],u.step+1));
}
}
}
}
int main()
{
freopen("room.in","r",stdin);
freopen("room.out","w",stdout);
cin>>n>>m>>k;
int x,y,z,t;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=k;j++)
{
cin>>x;
a[i]=a[i]*2+x;
}
}
for (int i=1;i<=m;i++)
{
cin>>y>>z;
t=0;
for (int j=1;j<=k;j++)
{
cin>>x;
t=t*2+x;
}
c[y].push_back(node1(z,t));
}
bfs();
}
莫队算法，专门开一篇填坑
HDU3400.在二维平面上有两条线段AB、CD。AB上的速度是P，CD上是Q，平面上的其他区域上速度为R。求A->D的最少时间。
由于我们必须在A出发，在D结束，所以我们必然会在两条线段上行走一段距离。而知道在这两条线段上分别应当走多少距离，就是这道题的关键。我们设点q，p分别是在AB CD上的两个点，暴力枚举这两个点的位置（即距离A、D的距离）显然是不行的。而面对求一个极值（在这题里是最短时间）的问题二分也不适用，于是我们就有了三分查找。
三分查找与二分相似。从名字就可以看出，三分的每次操作就是用两个点把当前的区间分成三个区间。即在二分查找的基础上，在右区间（或左区间）再进行一次二分。该算法通常用来迅速确定最值。二分查找所面向的搜索序列的要求是：具有单调性。而三分查找所面向的搜索序列的要求是：序列为一个凸性函数。即该序列必须有一个最大值（或最小值），在极值的左侧序列，必须满足不严格单调递增（递减），右侧序列必须满足不严格单调递减（递增）。如下图，表示一个有最大值的凸性函数：
（1）与二分法类似，先取整个区间的中间值mid。
（2）再取右侧区间的中间值midmid，从而把区间分为三个小区间。
（3）如果mid比midmid更靠近最值，我们就舍弃右区间，否则我们舍弃左区间。
比较mid与midmid谁最靠近最值，只需要确定mid所在的函数值与midmid所在的函数值的大小。当最值为最大值时，mid与midmid中较大的那个自然更为靠近最值。最值为最小值时同理。
（4）重复（1）（2）（3）直至找到最值。
挖个坑以后再填（逃）
先看数据范围，128*128？果断直接暴力模拟发射器的位置，但是在计算在(x-d,y-d)到(x+d,y+d)中的之和时要注意边界和范围。什么？代码呢？这么斯波的题自己去写。
这道题记得很早以前就做过。条件1如何解决是这道题的难点。如果直接对每个点进行判断能否抵达终点显然会超时的。那么既然我们要判断哪些点能到终点，为啥不从终点反着广搜一遍，看看终点能到哪些点呢？于是思路就显而易见了。将所有路径反向，从终点开始做一遍BFS标记出哪些点是可以作为合法路径，再做一遍spfa（其实貌似BFS也能过）就搞定了。
#include<bits/stdc++.h>
#define N 200005
#define inf 0x3f3f3f3f
using std::queue;
struct Edge{
int v,nxt;
}e[N],E[N];
int n,m,s,t;
int head[N],tot;
int h[N],tol;
void AddEdge(int u,int v){
e[++tot]=(Edge){v,head[u]};head[u]=tot;//正向边
E[++tol]=(Edge){u,h[v]};h[v]=tol;//反向边
}
int vis[N];//表示这个点能直接到达终点
int be[N];//if be[i]== true 表示i没有被删除
int tt;
int dfs(int x,int f){//反向遍历
vis[x]=true;
for(int i=h[x];i;i=E[i].nxt){//反向边
int to=E[i].v;
if(to==f)continue;
if(vis[to])continue;
dfs(to,x);
}
}
int init(){//删除不能存在于路径上的点
for(int i=1;i<=n;++i){
if(!vis[i])continue;bool flag=0;
for(int j=head[i];j;j=e[j].nxt){
int to=e[j].v;
if(!vis[to])flag=true;
}
if(!flag)be[i]=true;
}
}
int dis[N];
int spfa(int s,int t){// 从起点到终点的最短路
memset(dis,0x3f,sizeof(dis));
memset(vis,false,sizeof(vis));
int top,to;
dis[s]=0;queue<int>que;que.push(s);vis[s]=true;
while(!que.empty()){
top=que.front();
que.pop();
for(int i=head[top];i;i=e[i].nxt){
to=e[i].v;
if(!be[to])continue;
int l;
if(dis[top]+1<dis[to]){
dis[to]=dis[top]+1;
if(!vis[to]){
vis[to]=true;
que.push(to);
}
}
}
}
return dis[t];
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
int u,v;
scanf("%d%d",&u,&v);
AddEdge(u,v);
}
scanf("%d%d",&s,&t);
dfs(t,0);
init();
int ans=spfa(s,t);
if(ans==inf)ans=-1;
printf("%d\n",ans);
return 0;
}
狗比数学题。如果我们有个一元四次方程a0+a1x+a2x^2+a3x^4+a4x^4=0，那么其显然等于(x(x(xa4+a3)+a2)+a1)+a0=0。这就是一个叫做秦九韶的人提出的imba解法（这货是宋朝人!）。换句话讲，对于一个多项式，维护一个初始值为0的sum，每一次先加上当前的系数a，再自乘x，这个多项式如果和为0，则这是方程的一个解。但是这个a比较大（dark），高精度又容易被卡常，于是我们就可以先给a取模。这里我要介绍一个非常excited的素数：19260817，据信这个素数可以极大的优化程序的运行时间，通常为1s。
#include<bits/stdc++.h>
#define maxn 105
#define MOD1 23333
#define MOD2 19260817
using namespace std;
int n,m,a1[maxn],a2[maxn],vis[1000005];
vector<int>ans;
void read(int pos){
char c=getchar();
int x1=0,x2=0,f=1;
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x1=(x1*10+c-'0')%MOD1;
x2=(x2*10+c-'0')%MOD2;
c=getchar();
}
a1[pos]=x1*f;
a2[pos]=x2*f;
}
int check(int f[],int x,int mod) {
int y=0;
for(int i=n;i>=0;i--)
y=((long long)y*x+f[i])%mod;
return (!y)? 1:0;
}
int main(){
freopen("equation.in","r",stdin);
freopen("equation.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++)read(i);
for(int i=1;i<=MOD1;i++)
if(check(a1,i,MOD1))
for(int j=i;j<=m;j+=MOD1)
if(check(a2,j,MOD2))
vis[j]=1;
for(int i=1;i<=m;i++)
if(vis[i])ans.push_back(i);
printf("%d\n",ans.size());
for(int i=0;i<ans.size();i++)printf("%d\n",ans[i]);
return 0;
}