2019CSP-S1轮备战——程序题

根据教练给的几道题目，说是做完初赛就差不多了，但是蒟蒻这么菜，肯定是过不了的，然后就AFO了，但还是要再挣扎一下。。

T1 洛谷 1076寻宝

这题题意读懂以后就没有什么大问题了，就是纯模拟，然后蒟蒻点开题解，%了一份直接上交

/* P1076 寻宝 */
/* CSP-S2 普及/提高- - T1 */
/* Developed By 傻_逼 */
#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, m, a[10001][101], b[10001][101], c[10001], sum, k, ans, q;

int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
        f = (ch == '-') ? -1 : 1, ch = getchar();
    while (isdigit(ch))
        x = x * 10 + (ch - '0'), ch = getchar();
    return x * f;
}

signed main()
{
    n = read(), m = read();
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m - 1; j++)
            a[i][j] = read(), b[i][j] = read(), c[i] += a[i][j];
    k = read();
    for (int j = 1; j <= n; j++)
    {
        sum += b[j][k];
        ans = 0;
        q = k;
        b[j][q] = (b[j][q] - 1) % c[j] + 1;
        while (ans < b[j][q])
        {
            ans += a[j][k];
            if (ans == b[j][q])
                break;
            k++;
            if (k == m)
                k = 0;
        }
    }
    cout << sum % 20123;
}

T2 洛谷 P1077摆花

思考一会发现是一个背包
设f[i][j]表示前i盆花放了j盆的情况种数
f[i][j]=sigmaf[i-1][j-k],0<=k<=min(a[i],j);

/* P1077 摆花 */
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 110;
const int Mod = 1e6 + 7;
int n, m, a[maxn], f[maxn][maxn];
signed main()
{
    scanf("%d%d", &n, &m);
    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        for (int j = 0; j <= m; j++)
            for (int k = 0; k <= min(j, a[i]); k++)
                f[i][j] = (f[i][j] + f[i - 1][j - k]) % Mod;
    }
    cout << f[n][m] << '\n';
    return 0;
}

T3洛谷 P1965转圈游戏

看题之后可以得到答案为(x+m10^k)%n
即(x%n+m%n(10^k%n))%n
其中(10^k%n)用快速幂求解，最后输出即可

/* P1965 转圈游戏 */
/* CSP-S2 普及/提高- - T3 */
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, k, x;
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
        f = (ch == '-') ? -1 : 1, ch = getchar();
    while (isdigit(ch))
        x = x * 10 + (ch - '0'), ch = getchar();
    return x * f;
}
int QuickPow(int a, int b)
{
    int res = 1, t = a;
    while (b)
    {
        if (b & 1)
            res = res * t % n;
        t = t * t % n;
        b >>= 1;
    }
    return res;
}
signed main()
{
    n=read(),m=read(),k=read(),x=read();
    cout<<(x%n+m%n*QuickPow(10,k)%n)%n<<'\n';
    return 0;
}
/*
题意：
给出n,m,k,x
求(x+m*10^k)%n
k<=1e9,n<=1e6,m<n,x<n;
*/