头像

HalfSummer


访客:812

离线:3天前


问题 题目Twins

话说题库最后有很多名字一样的题,但数据范围不太一样

类似于

在逃的牛

牛的洗牌

牛奶测量

有些数据范围大一些能不能把名字改一下比如加个后缀xxx加强版




这道题就是一个纯模拟题,用朴素的模拟循环一百遍就行

$Tips$ :

  • 结构体表示更加方便

  • $if$语句中两个语句位置不要写反不然会$WA$(实践出真知)

  • $work$数组中由于第$i$个操作是第三的整数倍时$i$模$3$为$0$,所以要把第三个操作放在$0$位上

综上所述本题的时间复杂度就是O(常数)级别的,可以轻松AC此题

代码:

#include<iostream>
using namespace std;
struct bucket{
    int c, m;
};
bucket buc[10];
int work[3][3] = {{0,3,1},{0,1,2},{0,2,3}};
int main(){
    for(int i = 1;i <= 3;i ++){
        cin >> buc[i].c >> buc[i].m;
    }
    for(int i = 1;i <= 100;i ++){
        if(buc[work[i % 3][1]].m > (buc[work[i % 3][2]].c - buc[work[i % 3][2]].m)){
            buc[work[i % 3][1]].m = buc[work[i % 3][1]].m - (buc[work[i % 3][2]].c - buc[work[i % 3][2]].m) ;
            buc[work[i % 3][2]].m = buc[work[i % 3][2]].c;
        }
        else{
            buc[work[i % 3][2]].m += buc[work[i % 3][1]].m;
            buc[work[i % 3][1]].m = 0;
        }
    }
    for(int i = 1;i <= 3;i ++){
        cout << buc[i].m <<endl;
    }
}

点个赞再走呗




#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int gets(vector<int> num,int l,int r){
    int res = 0;
    for(int i = l;i >= r;i --){
        res = res * 10 + num[i];
    }
    return res;
}
int power10(int x){
    int res = 1;
    while(x --){
        res *= 10;
    }
    return res;
}
int count(int n,int x){
    if(!n) return 0;
    vector<int> num;
    while(n){
        num.push_back(n % 10);
        n /= 10;
    }
    n = num.size();
    int res = 0;
    for(int i = n - 1 - !x;i >= 0;i --){
        if(i < n - 1) {
            res += gets(num,n - 1,i + 1) * power10(i);
            if(!x) res -= power10(i);
        }
        if(num[i] == x) res += gets(num,i - 1,0) + 1;
        else if(num[i] > x) res += power10(i);
    }
    return res;
}
int main(){
    int a , b;
    while(cin >> a >> b , a || b){
        if(a > b) swap(a,b);
        for(int i = 0;i <= 9;i ++){
            printf("%d ",count(b,i) - count(a - 1,i));
        }
        printf("\n");
    }
} 



#include<iostream>
#include<cstdio>
#include<cstring>
#define Trump 250
#define Pig 250
using namespace std;
const int MaxM = 1 << 15;
long long f[15][MaxM];
bool st[MaxM];
int main() {
    int N,M;
    while(cin>>N>>M,N || M) {
        memset(st,true,sizeof st);
        memset(f , 0  ,sizeof f );
        for(int i = 0; i < 1 << N; i ++) {
            int cnt = 0;
            for(int j = 0; j < N;j ++){
                if(i >> j & 1 == 1) {
                    if(cnt & 1) {
                        st[i] = false;
                    } 
                    cnt = 0;
                } 
                else {
                    cnt ++;
                }
            } 
            if(cnt & 1){
                st[i] = false;
            }   
        }
        f[0][0] = 1;
        for(int i = 1; i <= M; i ++) {
            for(int j = 0; j < (1 << N); j ++) {
                for(int k = 0; k < (1 << N); k ++) {
                    if((j & k) == 0 && st[j | k]) f[i][j] += f[i-1][k];
                }
            }
        }
        cout<<f[M][0]<<endl;
    }
}






#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 6010;
int last[N],ne[N],edge[N],cnt;
int ha[N];
bool HF[N];
int f[N][2];
void add(int a, int b){
    edge[cnt] = b;
    ne[cnt] = last[a];
    last[a] = cnt++;
}
void MZBZY(int root){
    f[root][1] = ha[root];
    for(int i = last[root];i != -1;i = ne[i]){
        MZBZY(edge[i]);
        f[root][0]+=max(f[edge[i]][0],f[edge[i]][1]);
        f[root][1]+=f[edge[i]][0];
    }
}
int main(){
    memset(edge,-1,sizeof edge);
    memset(last,-1,sizeof last);
    int n;
    cin>>n;
    for(int i = 1;i <= n;i ++){
        cin>>ha[i];
    }
    for(int i = 1;i <= n - 1;i ++){
        int a,b;
        cin>>a>>b;
        add(b,a);
        HF[a] = true;
    }
    int root = 1;
    while(HF[root]) root++;
    MZBZY(root);
    cout<<max(f[root][0],f[root][1]);
}



#include<iostream>
#include<algorithm>
using namespace std;
int a[305], s[305];
int dp[305][305];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = a[i] + s[i - 1];
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int l = i, r = i + len - 1;
            dp[l][r] = 0x3f3f3f3f;
            for (int k = l; k < r; k++) {
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + s[r] - s[l - 1]);
            }
        }
    }
    cout << dp[1][n];
}



希望AcWing能够实现对自己做题的数量统计等等

望采纳




前面是神奇的快读

#include <iostream>
#include <vector>
#include <cstdio>
#include <deque>
#include <string>
#include <cstring>
using namespace std;
namespace io {
    const int __SIZE = (1 << 21) + 1;
    char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1, __c, qu[55]; int __f, qr, _eof;
    #define Gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
    inline void flush () { fwrite (obuf, 1, oS - obuf, stdout), oS = obuf; }
    inline void gc (char &x) { x = Gc(); }
    inline void pc (char x) { *oS ++ = x; if (oS == oT) flush (); }
    inline void pstr (const char *s) { int __len = strlen(s); for (__f = 0; __f < __len; ++__f) pc (s[__f]); }
    inline void gstr (char *s) { for(__c = Gc(); __c < 32 || __c > 126 || __c == ' ';)  __c = Gc();
        for(; __c > 31 && __c < 127 && __c != ' '; ++s, __c = Gc()) *s = __c; *s = 0; }
    template <class I> inline bool gi (I &x) { _eof = 0;
        for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc()) { if (__c == '-') __f = -1; _eof |= __c == EOF; }
        for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc()) x = x * 10 + (__c & 15), _eof |= __c == EOF; x *= __f; return !_eof; }
    template <class I> inline void print (I x) { if (!x) pc ('0'); if (x < 0) pc ('-'), x = -x;
        while (x) qu[++ qr] = x % 10 + '0',  x /= 10; while (qr) pc (qu[qr --]); }
    struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
} using io::pc; using io::gc; using io::pstr; using io::gstr; using io::gi; using io::print;
vector<int> nums;
vector<int> Max(vector<int> a,int k){
    vector<int> res;
    deque<int> q;
    for(int i=0;i < a.size();i++){
        if(!q.empty()&&q.front()<i-k+1) q.pop_front();
        while(!q.empty()&&a[q.back()]<a[i]) q.pop_back();
        q.push_back(i);
        if(i-k+1>=0) res.push_back(a[q.front()]);
    }
    return res;
}
vector<int> Min(vector<int> a,int k){
    vector<int> res;
    deque<int> q;
    for(int i=0;i < a.size();i++){
        if(!q.empty()&&q.front()<i-k+1) q.pop_front();
        while(!q.empty()&&a[q.back()]>a[i]) q.pop_back();
        q.push_back(i);
        if(i-k+1>=0) res.push_back(a[q.front()]);
    }
    return res;
}
int main(){
    std::ios::sync_with_stdio(false);
    int n,k;
    cin>>n>>k;
    int tp;
    for(int i=1;i<=n;i++){
        cin>>tp;
        nums.push_back(tp);
    }
    vector<int> max=Max(nums,k);
    vector<int> min=Min(nums,k);
    for(int i=0;i<min.size();i++){
        cout<<min[i]<<" ";
    }
    cout<<endl;
    for(int i=0;i<max.size();i++){
        cout<<max[i]<<" ";
    }
    return 0;
}



#include<iostream>
using namespace std;
long long pow(long long a , long long b, long long p){
    long long ans = 1, base = a;
    while(b != 0){
        if(b & 1 != 0){
            ans = ans * base % p; 
        }
        base = base * base % p;
        b >>= 1;
    }
    return ans;
}
int main(){
    long long a,b,p;
    cin>>a>>b>>p;
    if(b == 0) cout<< 1 % p ;
    else cout<<pow(a,b,p);
}



class Solution {
public:
    vector<int> maxInWindows(vector<int>& nums, int k) {
        vector<int> res;
    deque<int> q;
    for(int i=0;i < nums.size();i++){
        if(!q.empty()&&q.front()<i-k+1) q.pop_front();
        while(!q.empty()&&nums[q.back()]<nums[i]) q.pop_back();
        q.push_back(i);
        if(i-k+1>=0) res.push_back(nums[q.front()]);
    }
    return res;
    }
};