The Preliminary Contest for ICPC Asia Nanchang 2019

B Fire-Fighting Hero

题目链接
题意：英雄从给定的s点出发，求到所有救火点的最短路径最大值。消防员从k个出发点随便选一个出发，求到所有救火点的最短路径最大值。将两个值进行比较。英雄乘以系数1/c，比较大小。对于救火点来说，其余救火点消防员跑到相对应的点最短路径，每个点具有一个值，求其最大值。
思路：读错题意，原本就是很普通最短路。

#include <bits/stdc++.h>

#define maxn 1005
using namespace std;

int n, m, s, k, c;

struct edge {
    int to, cost;
};//定义边的结构体

typedef pair<int, int>P;//定义二元组 最短路径和顶点编号

vector <edge> G[maxn];//邻接表建图
int dis[maxn];//顶点最短路径
int di[maxn];
int v[maxn];

void dij(int a)
{
    priority_queue<P, vector<P>, greater<P> >q;//优先队列logn
                                               //可用fill(a,a+n,value)
    memset(dis, 0x3f, sizeof(dis));//将dis数组设为最大值
    dis[a] = 0;//起点为dis为0
    q.push(P(0, a));
    while (!q.empty())
    {
        P temp = q.top();
        q.pop();
        int v = temp.second;//获取最短路径顶点编号
        if (dis[v]<temp.first)continue;//判断dis是否小于路径
        for (int i = 0; i<G[v].size(); i++)
        {
            edge e = G[v][i];
            if (dis[e.to]>dis[v] + e.cost)//压缩路径
            {
                dis[e.to] = dis[v] + e.cost;
                q.push(P(dis[e.to], e.to));
            }
        }
    }
}

void input() {
    scanf("%d%d%d%d%d", &n, &m, &s, &k, &c);
    int i, j;

    for (i = 1; i <= n; i++)
        G[i].clear();
    for (i = 1; i <= k; i++)
        scanf("%d", &v[i]);

    int U, V, W;
    for (i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &U, &V, &W);
        G[U].push_back( { V, W });
        G[V].push_back( { U, W });
    }

    memset(di, 0x3f, sizeof di);
    for (i = 1; i <= k; i++) {
        dij(v[i]);
        for (j = 1; j <= n; j++)
            di[j] = min(di[j], dis[j]);
    }

    int v1=0,v2 = 0;
    for (i = 1; i <= n; i++)
        v2 = max(v2, di[i]);

    dij(s);
    for (i = 1; i <= n; i++)
        v1 = max(v1, dis[i]);

    if (v1 > v2*c)
        printf("%d\n", v2);
    else
        printf("%d\n", v1);

}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        input();
        //        solve();
    }
}

C Hello 2019

题目链接
题意：给定字符串，包含9012但不包含8012的字符串为好字符串，问对于一个[l,r]区间的子字符串变为好字符串需要最少删去多少个字母。
思路：将2、0、1、9、8变为矩阵，在矩阵上递推dp删去个数，以线段树形式维护前缀

#include <bits/stdc++.h>

#define maxn 200005 
using namespace std;

string s;
int n,m;

const int M=5;

struct Ma{
    int a[M][M];
    Ma(){
        memset(a,0x3f,sizeof a);
    }

    Ma operator*(const Ma& b)const{
        Ma ans;
        for(int k=0;k<M;k++)
            for(int i=0;i<M;i++)
                for(int j=0;j<M;j++)
                    ans.a[i][j]=min(ans.a[i][j],a[i][k]+b.a[k][j]);
        return ans;            
    }
};

struct node{
    int l,r;
    Ma a;
}t[maxn<<2];

void build(int l,int r,int rt){
    t[rt].l=l;
    t[rt].r=r;
    if(l==r){
        for(int i=0;i<M;i++)
            t[rt].a.a[i][i]=0;

        if(s[l]=='2'){
            t[rt].a.a[0][0]=1;
            t[rt].a.a[0][1]=0;
        }
        if(s[l]=='0'){
            t[rt].a.a[1][1]=1;
            t[rt].a.a[1][2]=0;
        }
        if(s[l]=='1'){
            t[rt].a.a[2][2]=1;
            t[rt].a.a[2][3]=0;
        }
        if(s[l]=='9'){
            t[rt].a.a[3][3]=1;
            t[rt].a.a[3][4]=0;
        }
        if(s[l]=='8'){
            t[rt].a.a[3][3]=1;
            t[rt].a.a[4][4]=1;
        }
        return ;
    }

    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    t[rt].a=t[rt<<1].a*t[rt<<1|1].a;

//    cout<<"***"<<rt<<endl;
//    for(int i=0;i<M;i++){
//        for(int j=0;j<M;j++)
//        {
//            if(t[rt].a.a[i][j]==1061109567)
//                cout<<"inf ";
//            else
//                cout<<t[rt].a.a[i][j]<<" ";
//        }    
//        cout<<endl;
//    }
//        
//    cout<<endl;
}

Ma query(int l,int r,int rt){
    if(l<=t[rt].l&&t[rt].r<=r)
        return t[rt].a;

    int mid=(t[rt].l+t[rt].r)>>1;
    if(mid>=r)
        return query(l,r,rt<<1);
    else if(mid<l)
        return query(l,r,rt<<1|1);
    else
        return query(l,r,rt<<1)*query(l,r,rt<<1|1);
}

void input(){
    scanf("%d%d",&n,&m);
    cin>>s;
    reverse(s.begin(),s.end());

    s=" "+s;
    build(1,n,1);

    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        int l=n+1-y;
        int r=n+1-x;
        Ma temp=query(l,r,1);
        int ans;
        if(temp.a[0][4]>n)
            ans=-1;
        else
            ans=temp.a[0][4];
        printf("%d\n",ans);
    }
}

int main(){
    input();
}

E Magic Master

题目链接
题意：桌子上有按顺序排列n张牌，我们需要循环进行以下操作，直到牌没有1、拿走第一张牌2、将最后一张牌拿到最前面的位置，循环m次。最终序列为1—n。求原序列下标的值。
思路：原序列经过以上步骤得到1-n。我们可以通过以上步骤得到此序列的倒置。模拟后，将查询离线排序。虽然时间复杂度算出来不对，但是依旧能神奇的过.

#include <bits/stdc++.h>

#define maxn 105
using namespace std;

int n,m;
int q;

struct node{
    int k,index,ans;
}qu[maxn];

bool cmp1(node a,node b){
    return a.k>b.k;
}

bool cmp2(node a,node b){
    return a.index<b.index;
}

void input(){
    scanf("%d%d",&n,&m);
    scanf("%d",&q);
    int i;
    for(i=1;i<=q;i++){
        scanf("%d",&qu[i].k);
        qu[i].index=i;
    }

    sort(qu+1,qu+1+q,cmp1);
} 

void solve(){
    queue <int>que;
    for(int i=n;i>=1;--i){
        if(!que.empty()){
            for(int j=1;j<=m;j++){
                int tmp=que.front();
                que.pop();
                que.push(tmp);
            }
        }
        que.push(i);
    }

    int cnt=1;
    for(int i=n;i>=1;i--){
        int tmp=que.front();
        que.pop();
        if(i==qu[cnt].k)
            qu[cnt++].ans=tmp;
        if(cnt>q)
            break;
    }

    sort(qu+1,qu+1+q,cmp2);
    for(int i=1;i<=q;i++){
        printf("%d\n",qu[i].ans);
    }
} 

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        input();
        solve();
    }
}

G Pangu Separates Heaven and Earth

题目链接
签到题

#include<bits/stdc++.h>
using namespace std;
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        if (n == 1) { puts("18000"); }
        else puts("0");
    }
}

H The Nth Item

题目链接
题意：对于给出第1项的查询q1得到答案a1=F[q1]。下一次的查询是q2=q1^a1，求第q次查询的答案。
思路：存在循环节，矩阵快速幂+记忆化map就可过。。。
正解，是推出O(1)的通项公式，快速幂求解。
图片说明 

#include <bits/stdc++.h>

#define maxn 10000005
typedef long long ll;
using namespace std;

const int p=998244353;

struct mat{
  long long m[2][2];
}ans,res;

//矩阵结构体
mat mul(mat a,mat b)
{
    mat tmp;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
          tmp.m[i][j]=0;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
          for(int k=0;k<2;k++)
            tmp.m[i][j]=(tmp.m[i][j]+(a.m[i][k]*b.m[k][j])%p)%p;
    return tmp;
}

unordered_map<ll, ll>mp;
//矩阵乘法
void quickpow(long long n)
{
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
        {
            if(i==j)ans.m[i][j]=1;
            else ans.m[i][j]=0;
        }
    while(n)
    {
        if(n&1LL)ans=mul(ans,res);
        res=mul(res,res);
        n=n>>1;
    }
    return;
}

int main(){
    ll q,n;
    scanf("%lld%lld",&q,&n);
    ll ANS=0,a;
    while(q--){

        if(mp.count(n))
        {
            a=mp[n];
        }else{
            res.m[0][0]=3;
            res.m[0][1]=2;
            res.m[1][0]=1;
            res.m[1][1]=0;

            quickpow(n-1);
            a=ans.m[0][0];
            mp[n]=a;
        }

//        for(int i=0;i<2;i++){
//            for(int j=0;j<2;j++)
//                cout<<ans.m[i][j]<<" ";
//            cout<<endl;
//        }
//        cout<<endl;

        n=n^(a*a);
        ANS=ANS^a;
    }
    printf("%lld\n",ANS);
}