T1 无线网络发射器选址
先看数据范围，128*128？果断直接暴力模拟发射器的位置，但是在计算在(x-d,y-d)到(x+d,y+d)中的之和时要注意边界和范围。什么？代码呢？这么斯波的题自己去写。
T2 联合权值
这道题记得很早以前就做过。条件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;
}
T3 解方程
狗比数学题。如果我们有个一元四次方程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;
}