A.打卡,下班!

用栈模拟,区域赛签到题,详情请看代码,数据可能有问题,被暴力A了,下面是正解

#include
using namespace std;

const int N = 100005;
int ans[N],a[N],S[N];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1;i <= n; ++i) {
        scanf("%d",&a[i]);
    }
    int loc = 0;
    for(int i = 1;i <= n; ++i) {
        while(loc && a[i] > a[S[loc]]) {
            ans[S[loc]] = i;
            --loc;
        }
        S[++loc] = i;
    }
    for(int i = 1;i <= n; ++i) {
        printf("%d%c",ans[i],i==n?'\n':' ');
    }
    return 0;
}

B.组合判断

预处理

#include
#include
#include
#include
#include
#include
#include

using namespace std;
#define ll long long

int t;
ll x;
map mp;

int main()
{
    srand((int)time(0));
    for(ll i = 1;i <= 10000; ++i) {
        mp[i*i*i*i] = true;
    }
    scanf("%d",&t);
    while(t--) {
        scanf("%lld",&x);
        bool fg = false;
        for(ll i = 1;i <= 10000; ++i) {
            if(mp[x-i*i*i*i]) {
                fg = true;
                break;
            }
            if(x-i*i*i*i < 0)
                break;
        }
        if(fg) {
            puts("YES");
        }
        else {
            puts("NO");
        }
    }
    return 0;
}

C.点菜吃饭

01背包变形

#include
using namespace std;
const int maxn=10005;
int dp[maxn],a[105],n,m;
int main(void)
{
    cin>>n>>m;
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;++i)
        cin>>a[i];
    dp[0]=1;
    for(int i=1;i<=n;++i)
        for(int j=m;j>=0;--j)
            if(j>=a[i])
            dp[j]+=dp[j-a[i]];
    cout<

D.简单斐波那契数列

矩阵快速幂,这个超范围了

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const long long N = 2;
const long long mod = 1e9 + 7;
long long n, k;

struct mat {
    long long m[N + 1][N + 1];
    mat() {
        memset(m, 0, sizeof(m));
        for(int i = 1; i <= N; i++)
            m[i][i] = 1;
    }
};

//矩阵乘法
mat multi(mat a, mat b) {
    mat c;
    memset(c.m, 0, sizeof(c.m));
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            for(int k = 1; k <= N; k++) {
                c.m[i][j] += a.m[i][k] * b.m[k][j] % mod;
                c.m[i][j] %= mod;
            }
        }
    }
    return c;
}
//矩阵快速幂
mat fastpow(mat a, long long k) {
    mat res;
    while(k) {
        if(k & 1) res = multi(a, res);
        a = multi(a, a);
        k >>= 1;
    }
    return res;
}
int main() {
    cin >> n;
    mat x;
    memset(x.m, 0, sizeof(x.m));
    x.m[1][1] = x.m[1][2] = x.m[2][1] = 1;
    mat ans;
    ans = fastpow(x, n - 1);
    printf("%lld\n", ans.m[1][1]);


    return 0;
}

E.傻蛋

简单的博弈论,傻蛋必输

#include
#include
using namespace std;
int main() {
    int t;
    cin>>t;
    while(t--)puts("0");
    return 0;
}


本当の声を響かせてよ