第一天的摸底考试海星。

T1想了半天想出的乱搞算法竟然是对的，两个哑铃分放上下两行的一定要取max记录答案，同一行但不相邻要把中间全部移走或把两个都移到别处，所以在中间取max，再和两端的哑铃取一下min，用线段树维护区间最值。

T2感觉似曾相识，看别人上来都写的这个就先写了写，所求看起来和方差差不多，就想想要是搞个平均值随便搞搞怎么样，对于实数平均值就四舍五入一下，试了试样例发现都对了，那么根据胡乱归纳法，目标值取平均数就是对的，懒得细想了直接写上去还确实对了。

T3写了一个比较简单的DP，从当前字符向前找，找到可行范围，利用可行范围内的值更新，超出可行范围直接跳出，O(n^2)算法竟然卡过了。正解是线段树优化的DP，但好像因为过了这道题就忘了写正解，现在也忘得差不多了，找时间补一下。

T4考场上怎么也没想出来，就拿了20分的送分，而且我发现我爆搜都打不好，T4T5打的爆搜样例都过不了，只能写一些最弱的送分…老师讲了以后才发现真的不难，主要这个思路见的比较少，但好像还是见过，忘记了……

T5好毒瘤啊，看wls的一连串if看的怀疑人生，问了mls才发现了陈溪大佬写的for循环版本，还是很简洁明了的，经老师一讲就更清楚了，不过不知道为什么他的跑了1660ms…可能是常数太大了，我稍微优化了下，防止了数组越界，加了并没有森么用的快读，903ms还是蛮快的……发现更快的大佬都是写的一连串if，最快的甚至快了3倍，可能是for循环有一些冗余状态吧，这题对我来说还是比较难的…加了些注释，当作是题解发出来？

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

const ll mo=998244353;
int n,m,i,j,k,l,a,b,c;
ll f[70][70][70][70],ans;
//f[i][a][b][c]：第i列，对于每一行，有a行有0个棋子，b行有1个棋子，c行有2个棋子时，的情况数 
inline char gc()
{
    static char buf[1000001],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2) ? EOF : *p1++;
}

inline void re(int &x)
{
    x=0;
    char ch=gc();
    while(ch<'0'||ch>'9') ch=gc();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48), ch=gc();
}

inline ll C(int x,int y)
{//C(n,m)=n!/((n-m)!*m!)
    switch(y)
    {
        case 0:
            return 1;//C(x,0)
        case 1:
            return x;//C(x,1)
        case 2:
            return 1ll*x*(x-1)/2;//C(x,2) 
        case 3:
            return 1ll*x*(x-1)*(x-2)/6;//C(x,3) 
        default:
            return 0;
    }
}

int main()
{
    re(n); re(m);//设n为列，m为行（不设也一样 
    f[0][m][0][0]=1;//第0列，当然只有所有行都是0个棋子这一种情况 
    for(i=0;i<=n;i++)//枚举每一列 
        for(j=0;j<=m;j++)//枚举0个棋子的行数 
            for(k=0;k<=m-j;k++)//枚举1个棋子的行数 
                for(l=0;l<=m-j-k;l++)//枚举2个棋子的行数 
                    if(i==n) ans=(ans+f[i][j][k][l])%mo;//到达了最后一列，累加答案 
                    else 
                        for(a=0;a<=min(j,3);a++)//枚举由0个棋子增加到1个棋子的行数，不能超过3个因为每列最多3个，当然也不能超过原来0个棋子的行数 
                            for(b=0;b<=min(k,3-a);b++)//枚举由1个棋子增加到2个棋子的行数 
                                for(c=0;c<=min(l,3-a-b);c++)//枚举由2个棋子增加到3个棋子的行数 
                                {//0个棋子的行数减少了a，1个棋子的行数增加了a减少了b，2个棋子的行数增加了b减少了c，这种情况即为当前状态所能更新的 
                                    f[i+1][j-a][k+a-b][l+b-c]+=f[i][j][k][l]*C(j,a)*C(k,b)*C(l,c);
                                    f[i+1][j-a][k+a-b][l+b-c]%=mo;//加上当前状态的情况数乘上在j行0个棋子的行中选a行，在k行1个棋子的行中选b行，在l行2个棋子的行中选c行的组合数想乘 
                                }
    printf("%lld",ans%mo);//输出答案 
    return 0;
}

T4这道题考试时乍看不算太难，然而细考虑时，总在想若路径上有较小的环怎么搞，本就弱的代码实现能力再去实现错误的想法结果当然是瞎搞……

正解的方法真的是很巧妙，也是见的太少，想不到，但对我来说还是有些难理解…问了老师，自己又思考很久才想通……

在写注释时还是不太清楚，写完注释自己就比较清楚了（虽然旁人可能看不清楚XD）

对于算法，只是spfa，但不是单纯的点队列，而是对于每个点的每种%的情况的队列，话不多说，都在码里了

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>//d：与起点相连的边上最短边长度*2，即为起点直连的1个最小的环 
//此题主要在于，对于长度为p的1到n的路径，若其存在从1到n的一条路径l，l的长度%d=p%d且l的长度<=p 
using namespace std;
//因为只要有这样的l，p即为先在起点连接的最小的环绕((p-l)/d)圈再走l那条路径 
typedef pair<int,int> PR;
#define mp make_pair
#define fi first
#define sc second

const int N=10010,M=20010,inf=0x3f3f3f3f;
int n,m,Q,p,t,Head[N],ver[M],cost[M],Next[M],tot=1,mi=100,f[N][110],d;
bool vis[N][110];//f[i][j]：由起点1开始，到i点，长度%d==j的路径中，最短的路径的长度 
queue <PR> q;

void re(int &x)
{
    x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
}

inline void add(int x,int y,int z)
{
    ver[++tot]=y; cost[tot]=z; Next[tot]=Head[x]; Head[x]=tot;
}

void spfa(int mo)
{//不需要担心路径过程中更小的环，spfa过程中会一圈一圈套出来，最后求出的f[i][j]定为到i，距离%d为j的最短距离 
    int i,x,disx,y,disy;
    memset(f,0x3f,sizeof(f));//初始化为最大值，以便后期更新 
    q.push(mp(1,0)); vis[1][0]=1; f[1][0]=0;//到点1的距离当然为0，%d也为0，入队 
    while(!q.empty())
    {
        x=q.front().fi; disx=q.front().sc; q.pop();//取出队首，x为当前点，disx为当前到当前点的最小距离%d的值 
        for(i=Head[x];i;i=Next[i])
        {
            y=ver[i]; disy=(disx+cost[i])%mo;//y为下一点，disy为由当前点到y算出的1到y的距离%d的值 
            if(f[x][disx]+cost[i]<f[y][disy])//松弛操作 
            {
                f[y][disy]=f[x][disx]+cost[i];
                if(!vis[y][disy])//从1到y，路径长%d为disy的情况，没有再队列中 
                {
                    vis[y][disy]=1;
                    q.push(mp(y,disy));//入队 
                }
            }
        }
        vis[x][disx]=0;//退队 
    }
}

int main()
{
    int u,v,w,i;
    re(n); re(m);
    for(i=1;i<=m;i++)
    {
        re(u); re(v); re(w);
        add(u,v,w);
        add(v,u,w);//无向边建双向 
    }
    d=inf;
    for(i=Head[1];i;i=Next[i]) d=min(d,cost[i]);//找到起点1的出边中最短的 
    re(Q);
    if(d==inf)//如果起点1压根就没有出边，那肯定都不行 
    {
        while(Q--) printf("AKTang!\n");
        return 0;
    }
    d*=2;//把最短的出边*2，变成最小的环 
    spfa(d);//以最小的环为模数进行spfa 
    while(Q--)
    {
        re(p);
        if(f[n][p%d]<=p) printf("AWaDa!\n");//如果可以通过绕d跑几圈，加上一个路径到n，总长为p，存在总长为p的路径 
        else printf("AKTang!\n");//否则不存在 
    }
    return 0;
}