第三届河北省大学生程序设计竞赛燕山大学选拔赛（下）

短命女 2022-01-13 12:39 218阅读 0赞

### 第三届河北省大学生程序设计竞赛燕山大学选拔赛（下） ###

*  MI
 *   *  问题描述
     *  输入格式
     *  输出格式
     *  输入样例
     *  输出样例
     *  数据范围及约定：
     *  题解
     *  源代码
     *   *  题解一：
         *  题解二：
 *  真·人口普查
 *   *  问题描述
     *  输入格式
     *  输出格式
     *  输入样例
     *  输出样例
     *  数据范围及约定：
     *  题解
     *  源代码
     *   *  题解一
         *  题解二
 *  P-range
 *   *  问题描述
     *  输入格式
     *  输出格式
     *  输入样例
     *  输出样例
     *  数据范围及约定：
     *  题解
     *  源代码
 *  小飒的聚会
 *   *  问题描述
     *  输入格式
     *  输出格式
     *  输入样例
     *  输出样例
     *  数据范围及约定：
     *  题解
     *  源代码

# MI #

## 问题描述 ##

给定底数a和指数n，求幂a^n的值
    但是这个幂可能很大，请输出它对100000213取模的结果

## 输入格式 ##

只有一行，输入两个用空格隔开的整数a和n

## 输出格式 ##

只有一行，输出一个整数，表示a^n对100000213取模的结果

## 输入样例 ##

2 3

## 输出样例 ##

## 数据范围及约定： ##

对于所有数据，保证a和n为正整数且1≤a≤10^6，1≤n≤10^100000

## 题解 ##

方法一：根据幂取模的性质通过对幂的每一位进行幂运算。
    方法二：由于模数是素数，可以根据费马小引理进行求解

## 源代码 ##

### 题解一： ###

#include <bits/stdc++.h>
    
    using namespace std;
    const int mod=100000213;
    long long quick_mod(long long a,long long b)
    { 
        long long ans=1;
        while(b){ 
            if(b&1){ 
                ans=(ans*a)%mod;
                b--;
            }
            b/=2;
            a=a*a%mod;
        }
        return ans;
    }//内部也用快速幂
    long long quickmod(long long a,char *b,int len)
    { 
        long long ans=1;
        while(len>0){ 
            if(b[len-1]!='0'){ 
                int s=b[len-1]-'0';
                ans=ans*quick_mod(a,s)%mod;
            }
            a=quick_mod(a,10)%mod;
            len--;
        }
        return ans;
    }
    
    int main(){ 
        char s[100005];
        int a;
        scanf("%d%s",&a,s);
        int slen=strlen(s);
        printf("%lld",quickmod(a,s,slen));
        return 0;
    }

### 题解二： ###

#include <bits/stdc++.h>
    
    using namespace std;
    const long long p = 100000213;
    
    long long quick_pow(long long a, long long n)
    { 
        a %= p;
        long long ans = 1;
        while(n)
        { 
            if(n&1) { ans = ans*a; ans %= p;}
            a = a*a;
            a %= p;
            n >>= 1;
        }
        return ans;
    }
    
    int main()
    {  
        long long a, n = 0; cin >> a;
        string str; cin >> str;
        for(int i = 0; i < str.size(); ++i) 
        { 
            n *= 10; n += str[i]-'0';
            n %= p-1;
        }
        cout << quick_pow(a, n) << endl;
        return 0;
    }

# 真·人口普查 #

## 问题描述 ##

假设有一列数 {Ai }(1 ≤ i ≤ n),1<=n<=300000 ，{Ai}的初始值均为0，要求支持如下两种操作：
    (1)将 A l至A r 的值均增加 x 。（ l,r,x 是输入的数）
    (2) 输出 A l +A l+1 +…+A r 。（ l, r 都是输入的数， l ≤ r ）
    根据操作要求进行正确操作并输出结果

## 输入格式 ##

第一行两个整数 n,m
    接下来m 行，每行描述一个操作，有如下两种情况：
    1 l r x(表示将A中[l,r]的值均增加x)
    2 l r (表示询问A中[l,r]的值的和)

## 输出格式 ##

对于每一个2号操作，输出结果

## 输入样例 ##

5 5
    1 1 1 30
    2 1 2
    1 1 5 6
    1 1 3 21
    2 4 4

## 输出样例 ##

30
    6

## 数据范围及约定： ##

对所有数据，保证n,m<=300000；1<=l<=r<=n；1<=x<=1000； 保证所有操作
    的左端点单调不降，并且所有询问的区间没有交集
    所有答案小于4611686018427387904

## 题解 ##

方法一：对于数据量不算太大的情况下，根据操作一的性质可知，可以利用差分的思想
    方法二：正解，利用数状数组进行求解

## 源代码 ##

### 题解一 ###

#include<stdio.h>
    typedef long long ll;
    const int MAXN=3e5+5;
    
    int main(){ 
        ll a[MAXN],x,x1,x2;
        int n ,m,flag,left,right;
        scanf("%d%d",&n,&m);
        for(int i=0;i<m;i++){ 
            scanf("%d",&flag);
            if(flag==1){ 
                scanf("%d%d%lld",&left,&right,&x);
                a[left]+=x;
                a[right+1]-=x;
            }
            else{ 
                scanf("%d%d",&left,&right);
                x = a[0];
                x1=x2=x;
                for(int i=1;i<=left-1;i++){ 
                    x+=a[i];
                    x1+=x;
                }
                for(int i=left;i<=right;i++){ 
                    x+=a[i];
                    x2+=x;
                }
                printf("%lld\n",x2);
            }
    	}
    }

### 题解二 ###

#include <bits/stdc++.h>
    using namespace std;
    
    long long tree1[300005],tree2[300005];
    inline int lowbit(int x) { return x&-x;}
    int n, m;
    
    void update(int p, long long x)
    { 
        long long pos = p;
        while(p <= n)
        { 
            tree1[p] += x; tree2[p] += pos*x;
            p += lowbit(p);
        }
    }
    
    long long query(int p)
    { 
        long long pos = p;
        long long ans = 0;
        while(p)
        { 
            ans += (pos+1)*tree1[p]-tree2[p];
            p -= lowbit(p);
        }
        return ans;
    }
    
    int main()
    { 
        scanf("%d%d",&n,&m);
        for(int i = 0; i < m; ++i)
        { 
            int op, l , r; scanf("%d%d%d",&op,&l,&r);
            if(op == 1)
            { 
                int x; scanf("%d",&x);
                update(l, x); update(r+1, -x);
            }
            if(op == 2)
    		printf("%lld\n",query(r)-query(l-1));
       }
        return 0;
    }

# P-range #

## 问题描述 ##

求给定的区间内有多少个数是素数

## 输入格式 ##

第一行：输入一个整数q，表示询问的总次数
    第二行~第q+1行：每行输入两个用空格隔开的整数a和b，表示区间边界（闭区间）

## 输出格式 ##

只有一行，输出q个用空格间隔的整数，表示给定区间内素数的个数

## 输入样例 ##

3
    1 2
    2 5
    1 10

## 输出样例 ##

1 3 4

## 数据范围及约定： ##

对于所有数据，保证1≤q≤10^6，0≤a,b≤10^8

## 题解 ##

由于题目给出的查询区间不止一个，所以需要筛选素数，而利用埃拉托斯特尼筛法筛选素数需要的空间大，
    所以利用欧拉筛法筛选数据，所需空间小，每次查询利用STL的提供的lower_bound和upper_bound
    找出所给区间的端点在素数数组的下标位置，相减即为结果

## 源代码 ##

#include<stdio.h>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int MAXN=1e8+8;
    const int MAXn=1e6;
    bool f[MAXN];
    int  a[MAXN];
    int index=0;
    void init(){ 
        for(int i=2;i<=MAXN;i++){ 
            if(!f[i])a[index++]=i;
            for(int j = 0;j<index&&i*a[j]<MAXN;j++){ 
                f[i*a[j]]=true;
    			if(i%a[j]==0)break;
    		}
        }
    }
    int main(){ 
        init();
        int n ,left,right;
        scanf("%d",&n);
        for(int i=0;i<n;i++){ 
            scanf("%d%d",&left,&right);
            if(left>right)swap(right,left);
        	int j = lower_bound(a,a+index,left)-a;
            int t = upper_bound(a,a+index,right)-a;
            printf("%d ",t-j);
    	}
    }

# 小飒的聚会 #

## 问题描述 ##

小飒同学想要从某地出发（1号点）去同学的家中参加一个party（n号点），他
    想让所用的时间尽量短，不过，令人费解的是，小飒同学从任何一个点出发都无
    法再回到这个点。现在，计算最短用时的这个任务就交给了你。

## 输入格式 ##

第一行，输入两个正整数n和m，分别表示图中的节点数和图中有向边的条数
    第二行~第m+1行，每行包含三个用空格隔开的整数a、b、c，表示从a点到b点有
    一条道路，穿越这条道路要花费c单位的时间

## 输出格式 ##

只有一行，包含一个整数，表示最短用时

## 输入样例 ##

4 4
    1 2 3
    1 3 4
    2 4 5
    3 4 6

## 输出样例 ##

## 数据范围及约定： ##

对于所有数据，保证2≤n≤10^5，1≤m≤5*10^5，1≤a,b≤n，|c|≤10^2

## 题解 ##

题目中“小飒同学从任何一个点出发都无法再回到这个点”这句话暗示着是有向
    边，且图不存在环路，可以看作AOV，根据拓扑排序求得拓扑序列，根据拓扑序列的顺序依次添加到最短路径，
    加入的时候判断是不是当前最小。最后得到d[1]便是最短用时

## 源代码 ##

#include <bits/stdc++.h>
    
    using namespace std;
    const int maxn = int(1e7+50);
    vector<int> av;
    struct Edge
    { 
        int u, v, w;
        Edge(int a, int b, int c):u(a), v(b), w(c){ }
    };
    
    vector<Edge> edges;
    vector<int> G[maxn];
    vector<int> l;
    int d[maxn];
    int n,m;
    int in[maxn];
    int rrr; 
    int main()
    { 
    
        cin>>n>>m;
        
        for(int i=0;i<m;i++)
        { 
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            edges.emplace_back(u, v, w);
            G[u].push_back(edges.size()-1);
            in[v]++;
        }
    
        queue<int> Q;
        for(int i = 1; i <= n; ++i) if(in[i] == 0) Q.push(i);
        while(!Q.empty())
        { 
            int x = Q.front();
            Q.pop();
            l.push_back(x);
            for(int i = 0; i < G[x].size(); ++i)
            { 
                const Edge &m = edges[G[x][i]];
                in[m.v]--;
                if(in[m.v] == 0) Q.push(m.v);
            }
        }
        for(int i = 0; i < maxn; ++i) d[i] = 0x3f3f3f3f;
        d[n] = 0;
    
        for(int i = l.size()-1; i >= 0; --i)
        { 
            int u = l[i];
            for(int i = 0; i < G[u].size(); ++i)
            { 
                const Edge &m = edges[G[u][i]];
                d[u] = min(d[u], d[m.v]+m.w);
            }
        }
        cout << d[1] << endl;
        return 0;
    }