《华东交通大学2018年ACM“双基”程序设计竞赛*补》

A：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double ld;
typedef pair<int,int> pii;
const int N = 205;
const int M = 1e6+5;
const LL Mod = 998244353;
#define rg register
#define pi acos(-1)
#define INF 1e9
#define INM INT_MIN
#define dbg(ax) cout << "now this num is " << ax << endl;
inline int read()
{
    int x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
    return x*f;
}
int main() 
{
    cout << "ecjtuacm" << "\n";
    //system("pause");
    return 0;
}
View Code

B：

因为n很小，可以直接递推。

但是也可以矩阵快速幂递推。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double ld;
typedef pair<int,int> pii;
const int N = 1e3+5;
const int M = 5e4+5;
const LL Mod = 1e9+7;
#define rg register
#define pi acos(-1)
#define INF 1e9
#define INM INT_MIN
#define dbg(ax) cout << "now this num is " << ax << endl;
struct Mat{
    LL m[5][5];
    Mat operator * (const Mat &a)const{
        Mat c;memset(c.m,0,sizeof(c.m));
        for(int i = 0;i < 4;++i)
            for(int j = 0;j < 4;++j)
                for(int k = 0;k < 4;++k) c.m[i][j] = (c.m[i][j]+m[i][k]*a.m[k][j]%Mod)%Mod;
        return c;
    }
};
LL ta[5][5] = {
{2,3,1,1},
{1,0,0,0},
{0,0,1,1},
{0,0,0,1},
};
Mat Mat_qm(Mat a,LL b)
{
    Mat res;memset(res.m,0,sizeof(res.m));
    for(int i = 0;i < 5;++i) res.m[i][i] = 1;
    while(b)
    {
        if(b&1) res = res*a;
        a = a*a;
        b >>= 1;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n;
    while(cin >> n,n)
    {
        Mat ans;memset(ans.m,0,sizeof(ans.m));
        for(int i = 0;i < 5;++i)
            for(int j = 0;j < 5;++j) ans.m[i][j] = ta[i][j];
        if(n == 1) printf("1\n");
        else if(n == 2) printf("2\n");
        else
        {
            ans = Mat_qm(ans,n-2);
            LL sum = 0;
            sum = (sum+2*ans.m[0][0])%Mod;
            sum = (sum+1*ans.m[0][1])%Mod;
            sum = (sum+2*ans.m[0][2])%Mod;
            sum = (sum+1*ans.m[0][3])%Mod;
            printf("%lld\n",sum);
        }
    }
 //   system("pause");
    return 0;
}
View Code

C：

显然是矩阵快速幂。

把f[n]转换到f[n-1]和f[n-2]。那么就可以变形为。

$g[n+1] = g[n] + 2f[n] + 3f[n-1] + n^2 + 3n + 2n^0$注意常数项看成0次。

矩阵快速幂递推即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double ld;
typedef pair<int,int> pii;
const int N = 1e3+5;
const int M = 5e4+5;
const LL Mod = 1e9+7;
#define rg register
#define pi acos(-1)
#define INF 1e9
#define INM INT_MIN
#define dbg(ax) cout << "now this num is " << ax << endl;
struct Mat{
    LL m[10][10];
    Mat operator * (const Mat &a)const{
        Mat c;memset(c.m,0,sizeof(c.m));
        for(int i = 0;i < 6;++i)
            for(int j = 0;j < 6;++j)
                for(int k = 0;k < 6;++k) c.m[i][j] = (c.m[i][j]+m[i][k]*a.m[k][j]%Mod)%Mod;
        return c;
    }
};
LL ta[10][10] = {
{1,2,3,1,3,2},
{0,2,3,0,1,1},
{0,1,0,0,0,0},
{0,0,0,1,2,1},
{0,0,0,0,1,1},
{0,0,0,0,0,1},
};
Mat Mat_qm(Mat a,LL b)
{
    Mat res;memset(res.m,0,sizeof(res.m));
    for(int i = 0;i < 6;++i) res.m[i][i] = 1;
    while(b)
    {
        if(b&1) res = res*a;
        a = a*a;
        b >>= 1;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    LL n;
    while(cin >> n,n)
    {
        if(n == 1) printf("2\n");
        else if(n == 2) printf("8\n");
        else
        {
            Mat ans;memset(ans.m,0,sizeof(ans.m));
            for(int i = 0;i < 6;++i)
             for(int j = 0;j < 6;++j) ans.m[i][j] = ta[i][j];
            ans = Mat_qm(ans,n-2);
            LL sum = 0;
            sum = (sum+ans.m[0][0]*8%Mod)%Mod;
            sum = (sum+ans.m[0][1]*2%Mod)%Mod;
            sum = (sum+ans.m[0][2]*1%Mod)%Mod;
            sum = (sum+ans.m[0][3]*4%Mod)%Mod;
            sum = (sum+ans.m[0][4]*2%Mod)%Mod;
            sum = (sum+ans.m[0][5]*1%Mod)%Mod;
            printf("%lld\n",sum);
        } 
    }
   // system("pause");
    return 0;
}
View Code

D：

注意，拿走了一张牌后，对于这张牌另一个人不可能拿到。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double ld;
typedef pair<int,int> pii;
const int N = 205;
const int M = 1e6+5;
const LL Mod = 1e9+7;
#define rg register
#define pi acos(-1)
#define INF 1e9
#define INM INT_MIN
#define dbg(ax) cout << "now this num is " << ax << endl;
inline int read()
{
    int x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
    return x*f;
}
int main()
{
    int a,b;
    while(~scanf("%d %d",&a,&b),a != -1 && b != -1)
    {
        if(a == 0) printf("%s\n",b == 1 ? "owatta" : "1");
        else
        {
            int ma,all = 42;
            if(b == 1) ma = 21-a;
            else ma = 20+a-1;
            ma++;
            int gcd = __gcd(ma,all);
            ma /= gcd,all /= gcd;
            printf("%d/%d\n",ma,all);
        }
    }
  //  system("pause");
    return 0;
}
View Code

G：

数位dp

可以发现，如果这个数满足是777...的倍数并且是数位和是777....的倍数。

那么他肯定满足时是7的倍数且数位和是7的倍数。

那么我们用dp[i][10][10]来表示到了i位时，这个数对7取模和数位和对7取模。

这里从最高位dp到最低位，我们最先会遍历完所有情况，满足数位dp的思想。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double ld;
typedef pair<int,int> pii;
const int N = 1e3+5;
const int M = 5e4+5;
const LL Mod = 1e9+7;
#define rg register
#define pi acos(-1)
#define INF 1e9
#define INM INT_MIN
#define dbg(ax) cout << "now this num is " << ax << endl;
LL dp[20][10][10],n,m;
int a[20];
LL dfs(int pos,int sum1,int sum2,bool limit)
{
    if(pos == 0) return (sum1 % 7 == 0 && sum2 % 7 == 0) ? 1 : 0;
    if(!limit && dp[pos][sum1][sum2] != -1) return dp[pos][sum1][sum2];
    int up = limit ? a[pos] : 9;
    LL ans = 0;
    for(int i = 0;i <= up;++i)
    {
        ans += dfs(pos-1,(sum1*10+i)%7,(sum2+i)%7,limit && i == a[pos]);
    }
    if(!limit) dp[pos][sum1][sum2] = ans;
    return ans;
}
LL slove(LL x)
{
    int len = 0;
    while(x)
    {
        a[++len] = x%10;
        x /= 10;
    }
    return dfs(len,0,0,true);
}
int main()
{
    memset(dp,-1,sizeof(dp));
    while(scanf("%lld %lld",&n,&m),n || m)
    {
        printf("%lld\n",slove(m)-slove(n-1));
    }
   // system("pause");
    return 0;
}
View Code

I:

有欧拉定理扩展：对于一个数，与其互质的数的总和总是euler(n)*n/2(注意是在1~n范围内的数)

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double ld;
typedef pair<int,int> pii;
const int N = 205;
const int M = 1e6+5;
const LL Mod = 1e9+7;
#define rg register
#define pi acos(-1)
#define INF 1e9
#define INM INT_MIN
#define dbg(ax) cout << "now this num is " << ax << endl;
inline int read()
{
    int x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
    return x*f;
}
LL quick_mi(LL a,LL b)
{
    LL re = 1;
    while(b)
    {
        if(b&1) re = re*a%Mod;
        a = a*a%Mod;
        b >>= 1;
    }
    return re;
}
LL euler(LL n)
{
    LL ans = n;
    LL m = sqrt(n);
    for(LL i = 2;i <= m;++i)
    {
        if(n%i == 0)
        {
            ans = ans/i*(i-1);
            while(n%i == 0) n /= i;
        }
    }
    if(n != 1) ans = ans/n*(n-1);
    return ans;
}
int main()
{
    LL n;
    while(~scanf("%lld",&n))
    {
        if(n == 1) printf("0\n");
        else
        {
            LL inv = quick_mi(2,Mod-2);
            LL ma1 = (((n%Mod)*((n+1)%Mod))%Mod*inv%Mod+Mod)%Mod;
            LL ma2 = (((euler(n)%Mod)*(n%Mod))%Mod*inv%Mod+Mod)%Mod;
            LL ans = (ma1-ma2+Mod)%Mod;
            printf("%lld\n",ans);
        }
    }
  //system("pause");
    return 0;
}
View Code

J：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double ld;
typedef pair<int,int> pii;
const int N = 205;
const int M = 1e6+5;
const LL Mod = 1e9+7;
#define rg register
#define pi acos(-1)
#define INF 1e9
#define INM INT_MIN
#define dbg(ax) cout << "now this num is " << ax << endl;
inline int read()
{
    int x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
    return x*f;
}
int a[15];
int main() 
{
    while(cin >> a[1])
    {
        for(int i = 2;i <= 10;++i) a[i] = read();
        int s = 1;
        for(int i = 1;i <= 10;++i)
        {
            if(a[i] == 1)
            {
                if(s != 5) s++;
            }
            else if(a[i] == 7)
            {
                if(s != -1) s--;
            }
        }
        if(s >= 5) printf("666\n");
        else printf("777\n");
    }
   // system("pause");
    return 0;
}
View Code

K：

最短路模改下就行

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double ld;
typedef pair<int,int> pii;
const int N = 205;
const int M = 1e6+5;
const LL Mod = 998244353;
#define rg register
#define pi acos(-1)
#define INF 1e9
#define INM INT_MIN
#define dbg(ax) cout << "now this num is " << ax << endl;
inline int read()
{
    int x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
    return x*f;
}
int n,m,dis[N];//dis[i]到i需要的最少花费
struct Node{int to,dis;};
vector<Node> G[N];
void slove()
{
    for(int i = 1;i <= n;++i) dis[i] = INF;
    dis[1] = 0;
    priority_queue<pii,vector<pii>,greater<pii> > Q;
    Q.push(pii{dis[1],1});
    while(!Q.empty())
    {
        int u = Q.top().second;
        int d = Q.top().first;
        Q.pop();
        if(d > dis[u]) continue;
        for(auto v : G[u])
        {
            if(dis[v.to] > max(dis[u],v.dis))
            {
                dis[v.to] = max(dis[u],v.dis);
                Q.push(pii{dis[v.to],v.to});
            }
        }
    }
}
int main() 
{
    while(~scanf("%d %d",&n,&m))
    {
        for(int i = 1;i <= n;++i) G[i].clear();
        while(m--)
        {
            int x,y,z;
            x = read(),y = read(),z = read();
            G[x].push_back(Node{y,z});
        }
        slove();
        printf("%d\n",dis[n]);
    }
    //system("pause");
    return 0;
}
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/zwjzwj/p/13462472.html