2019 The Preliminary Contest for ICPC Asia Nanjing

B　　题目链接

题目公式貌似复杂但实际拆解后就是power tower问题，见此处 。 想到用欧拉降幂，但是降幂时幂数的处理有点麻烦。

有一种精巧取模方式及其证明过程，见某位大哥的证明过程 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6;
int tot=0;
bool vis[maxn+6];
int prime[maxn+6],totient[maxn+6];
ll a,b,m;
ll mmod(ll x,ll m){
    return x>=m?(x%m+m):x;
}

ll qPow(ll a,ll b,ll m){
    ll ret = 1ll;
    while(b){
        if(b&1) ret = mmod(ret*a,m);
        a = mmod(a*a,m);
        b >>= 1;
    }
    return ret;
}

void init(){
    totient[1] = 1;
    vis[1] = true;
    for(int i=2;i<=maxn;++i){
        if(!vis[i]){
            vis[i] = true;
            prime[tot++] = i;
            totient[i] = i-1;
        }
        for(int j=0;j<tot;++j){
            if(i*prime[j]>maxn) break;
            vis[i*prime[j]] = true;
            if(i%prime[j]){
                totient[i*prime[j]] = totient[i] * (prime[j] - 1);
            }else{
                totient[i*prime[j]] = totient[i] * prime[j];
                break;
            }
        }
    }
//    printf("tot %d
",tot);
//    for(int i=1;i<=100;++i)
//        cerr<<totient[i]<<endl;
}

ll solve(ll L ,ll R, ll p ){
    if(L==R||p==1) return mmod(a,p);
    ll ret = qPow(a,solve(L+1,R,totient[p]),p);
//    printf("%lld %lld %lld %lld
",L,R,p,ret);
    return ret;
}

int main(){
    int T;
    scanf("%d",&T);
    init();
    while(T--){
        scanf("%lld%lld%lld",&a,&b,&m);
        if(b==0)
            printf("%lld
",1ll%m);
        else
            printf("%lld
",solve(1ll,b,m)%m);
    }
    return 0;
}

这大概算是欧拉定理的活用吧。

F　　题目链接

题目大意是给出 n 的 permutation  , 对于每一个元素 在其左右各不超过 K个数的范围里 递归地转移到不超过当前元素的最大元素上，若无则结束寻找，现在需要根据该permutation得到每一个元素的寻找链的长度。(T<=20;n,K<=1e5)

每个元素第一个寻找的下一个位置是固定的，用尺取法+set二分 可以预处理出所有元素的第一个元素的下一个位置 <O(nlogn)>，然后记忆化搜索即可<O(n)> 。因为搜到一个点后其后的转移是固定的。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;

set< int > S;
int N,K;
int permut[maxn];
int lefnext[maxn],rignext[maxn];
//bool vis[maxn];
int ans[maxn];

int getnext(int val){
    val = -val;
//    auto ptr = upper_bound(S.begin(),S.end(),val);//正是此处增加了复杂度
    auto ptr = S.find(val);
    ptr++;
    if(ptr == S.end()) return 0;
    int ret =  (*ptr);
    ret = -ret;
    return ret;
}

int DFS(int x){
//    printf("in DFS %d
",x);
    if(x<=0)
        return 0;
    if(ans[x])
        return ans[x];
    int LRnext = max(lefnext[x],rignext[x]);
    if(LRnext == 0)
        return ans[x] = 1;
    else
        return ans[x] = DFS(LRnext) + 1;
}

int main(){
//    __clock_t stt = clock();
//    __clock_t mdt;
    int T;
    scanf("%d",&T);
    while(T--){
        S.clear();
        scanf("%d%d",&N,&K);
        for (int i = 1; i <= N; ++i) {
            scanf("%d",&permut[i]);
            lefnext[i] = rignext[i] = 0;
//            vis[i] = false;
            ans[i] = 0;
        }

        int L,R;
        L = 1,R=1;
        S.insert(-permut[R]);
        lefnext[permut[R]] = getnext(permut[R]);
        while(L<=N&&R<=R){
            if(R-L+1 == K+1 || R==N){
                rignext[permut[L]] = getnext(permut[L]);
                S.erase(-permut[L]);
                L++;
            }
            else{
                R++;
                S.insert(-permut[R]);
                lefnext[permut[R]] = getnext(permut[R]);
            }
        }

//        mdt = clock();

        for(int i=1;i<=N;++i){
//            printf("%d : %d,%d
",i,lefnext[i],rignext[i]);
            ans[i] = DFS(i);
        }
        for(int i=1;i<=N;++i)
            printf("%d%c",ans[i],i==N?'
':' ');
    }
//    __clock_t ent = clock();
//    printf("%.3lf
", static_cast<double>(mdt - stt)/1000.0 );
//    printf("%.3lf
", static_cast<double>(ent - stt)/1000.0 );
    return 0;
}

然而开始写的复杂度却惊人的大，后来通过随机大数据调试发现问题出在了，这一句上:

auto ptr = upper_bound(S.begin(),S.end(),val);//正是此处增加了复杂度

换成 "ptr = S.find(val)  ; ptr ++ ;" 后就是正常预估的复杂度。 ps : 要是 S中没有 val 怎么办？也可以先insert后再erase()。

实际上最简单的写法是：

auto ptr = S.upper_bound(val);

如此也是对的。

std::upper_bound() 与 std::set::upper_bound() 完全不同啊。要是用第一个虽然答案无异，但相当于搜了许多不必要的位置，增加了时间开销。（set不是线性存储）

H　　题目链接

签到题。

给一个保证无负环但可能有负权边的DAG，依次给出六个询问，每个询问给出 u ，v （保证 u -> v之前无边）两点点号， 要求在该图上建立一条 u -> v 的带权边，权值最小且必须保证加边后图仍无负环，对于每隔询问进行加边操作且回答加边权值。

以v为起点跑 Bellman-Ford  ，然后 使加 u -> v后得到一个零权重环即可。v 到 u 是最短路，所以加新边 u -> v后 即使有其他环其权重也必然大于等于零。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Edge
{
    int from,to;
    ll dist;
};
vector<Edge> edges;
vector<int> g[1005];
bool inq[1005];
ll d[1005];
int pre[1005];
int cnt[1005];
int n,m;
int a,b;
void init()
{
    for(int i=0;i<=n-1;i++)
        g[i].clear();
    edges.clear();
}
void addedge(int from,int to,ll dist)
{
    edges.push_back((Edge){from,to,dist});
    int num=edges.size();
    g[from].push_back(num-1);
}
bool spfa(int s)
{
    queue<int> q;
    memset(inq,0,sizeof(inq));
    memset(cnt,0,sizeof(cnt));
    memset(d,0x3f,sizeof(d));
    d[s]=0;
    inq[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        inq[u]=0;
        for(int i=0;i<g[u].size();i++)
        {
            Edge e=edges[g[u][i]];
            if(d[e.to]>d[u]+e.dist)
            {
                d[e.to]=d[u]+e.dist;
                pre[e.to]=g[u][i];
                if(!inq[e.to])
                {
                    q.push(e.to);
                    inq[e.to]=1;
                    if(++cnt[e.to]>n)
                        return false;
                }
            }
        }
    }
    return true;
}

int main()
{
    int T;
    scanf("%d",&T);
    while (T--) {
        scanf("%d%d",&n,&m);
        init();
        for(int i=0;i<=m-1;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            addedge(a,b,c);
        }
        for (int i = 0; i < 6; ++i) {
            scanf("%d%d",&a,&b);
            if(spfa(b))
            {
                if(d[a] == d[1004]) d[a] = -1000000000;//无路径
                ll wei = d[a];
                printf("%lld
",-1*d[a]);
                addedge(a,b,-1*d[a]);
            }
        }

    }
    return 0;
}