竞赛讨论区 > 本次比赛的题解(比较简陋)

本次比赛的题解(比较简陋)

头像
td1336065617
发布于 07-31 18:15 APP内打开
赞 0 | 收藏 0 | 回复2 | 浏览458
A
#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include <string.h>
#include<map>
#include <vector>
#include<queue>
#include <iostream>
#include <vector>
using namespace std;
int dp[20010], bf[20010], qc[1000000], n, V;
struct ***bsp;{
    int v, w, s;
}wp[1000000];
int main()
{
    //freopen("1.out", " w ", stdout);
    //freopen("1.in", " r ", stdin);
    cin >> n >> V;
    for (int i = 1; i <= n; i++)
    {
        cin >> wp[i].v >> wp[i].w >> wp[i].s;
    }
    int jl = 0;
    for (int i = 1; i <= n; i++)
    {
        memcpy(bf, dp, sizeof(dp));
        for (int j = 0; j < wp[i].v; j++)
        {
            int dt = 0, dw = -1;
            for (int k = j; k <= V; k += wp[i].v)
            {
                while (dt <= dw && qc[dt] < k - wp[i].s * wp[i].v)
                {
                    dt++;
                }
                if (dt <= dw)
                    dp[k] = max(bf[k], bf[qc[dt]] + (k - qc[dt]) / wp[i].v * wp[i].w);
                while (dt <= dw && bf[k] >= bf[qc[dw]] + (k - qc[dw]) / wp[i].v * wp[i].w)dw--;
                qc[++dw] = k;
                jl++;
            }
        }
        
        //cout << i << ":" << dp[V]<<endl;
    }
    cout << dp[V];
    //cout << jl;
}


B
#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include <string>
#include <string.h>
#include<map>
#include <vector>
#include<queue>
#include<stack>
#include <iostream>
#include <vector>
#include<list>
using namespace std;
long long int n,k,maxa;
int main() {
     //freopen("5.out", " w ", stdout);
     //freopen("5.in", " r ", stdin);
    cin >> n>>k;
    if(n>1e6||n<1)
    {
        return -1;
    }
    if(k>1e18||k<1)
    {
        return -1;
    }
    for (int i = 0; i < n; i++)
    {
        long long int q;
        cin >> q;
        if(q>1e18||q<1)
    {
        return -1;
    }
        maxa = max(maxa, q);
    }
    k = max((long long int)(0), maxa - k);
    cout << k;
}


C
#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include <string>
#include<map>
#include <vector>
#include<queue>
#include <iostream>
#include <vector>
int main() {
    //freopen("7.out", " w ", stdout);
    //freopen("7.in", " r ", stdin);
    int n;
    std::cin >> n;
    std::vector<int> s(n);
    std::vector<std::vector<int>> dp(1000, std::vector<int>(1000));
    for (int i = 0; i < n; i++)
        std::cin >> s[i];
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        int a = s[i] / 1000, b = s[i] % 1000;
        a = 999 - a;
        b = 999 - b;
        int aa = a / 100, ab = a / 10 % 10, ac = a % 10;
        int ba = b / 100, bb = b / 10 % 10, bc = b % 10;
        a = 999 - a;
        b = 999 - b;
        for (int j = 0; j <= ba; j++)
            for (int k = 0; k <= bb; k++)
                for (int l = 0; l <= bc; l++)
                    ans += dp[a][j * 100 + 10 * k + l];
        for (int j = 0; j <= aa; j++)
            for (int k = 0; k <= ab; k++)
                for (int l = 0; l <= ac; l++)
                    dp[j * 100 + 10 * k + l][b]++;
    }
    std::cout << ans << std::endl;
    return 0;
}


D
#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include <string>
#include <string.h>
#include<map>
#include <vector>
#include<queue>
#include<stack>
#include <iostream>
#include <vector>
#include<list>
using namespace std;
typedef long long int ll;
namespace FAST_IO {
#define IN_LEN 250000
#define OUT_LEN 250000
    //以上两个值无需修改
    inline char Getchar() {
        static char buf[IN_LEN], * l = buf, * r = buf;
        if (l == r) r = (l = buf) + fread(buf, 1, IN_LEN, stdin);
        return (l == r) ? EOF : *l++;
    }
    char obuf[OUT_LEN], * ooh = obuf;
    inline void Putchar(char c) {
        if (ooh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh = obuf;
        *ooh++ = c;
    }
    inline ll rd() {
        ll x = 0; int ch = Getchar(); bool f = 1;
        while (!isdigit(ch) && (ch != '-') && (ch != EOF)) ch = Getchar();
        if (ch == '-') { f = 0; ch = Getchar(); }
        while (isdigit(ch)) { x = (x << 1) + (x << 3) + ch - '0'; ch = Getchar(); }
        return f ? x : -x;
    }
    void write(ll x) { if (x >= 10) write(x / 10), Putchar((char)(x % 10 + '0')); else Putchar((char)(x + '0')); }
    inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }
}
using namespace FAST_IO;
long long int n,num;
int main() {
    // freopen("5.out", " w ", stdout);
    // freopen("5.in", " r ", stdin);
     n = rd();
     if (n > 3e7 || n < 1)
         return -1;
     for (int i = 0; i < n; i++)
     {
         long long int zj = rd();
         num += (zj);
         if ( zj> 1e8 || n < 0)
             return -1;
     }
     cout << num;
}

E
#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include <string>
#include <string.h>
#include<map>
#include <vector>
#include<queue>
#include<stack>
#include <iostream>
#include <vector>
#include<list>
using namespace std;
 int n, m;
int cf[1000000], maxc;
int main() {
    //freopen("11.out", " w ", stdout);
    //freopen("11.in", " r ", stdin);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int h1, m1, s1, h2, m2, s2;
        scanf("%d:%d:%d - %d:%d:%d", &h1, &m1, &s1, &h2, &m2, &s2);
        int time1=h1*60*60+m1*60+s1, time2=h2*60*60+m2*60+s2;
        cf[time1] += 1;
        cf[time2+1] -=1;
        m=max(time2 + 1,m);
    }
    for (int i = 1; i <= m; i++)
    {
        cf[i] += cf[i - 1];
        maxc = max(cf[i], maxc);
    }
    cout << maxc;
}

F
#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include <string>
#include <string.h>
#include<map>
#include <vector>
#include<queue>
#include<stack>
#include <iostream>
#include <vector>
#include<list>
using namespace std;
int num;
int main() {
    int n;
    //freopen("5.out", " w ", stdout);
    //freopen("5.in", " r ", stdin);
    cin >> n;
    if(1000<n||n<1)
    {
        return-1;
    }
    while (n--)
    {
        string s;
        cin >> s;
        if (s.find("month") != s.npos)
        {
            num++;
        }
        if(1000<s.length()||s.length()<1)
    {
        return-1;
    }
    }
    cout << num;
}

G
#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include <string>
#include <string.h>
#include<map>
#include <vector>
#include<queue>
#include<stack>
#include <iostream>
#include <vector>
#include<list>
using namespace std;
map<long long int, long long int>bcj;
map<long long int,int>xb;
map<long long int, int>bcjh;
long long int find(long long int fd) {
    return bcj[fd] == fd ? fd : bcj[fd] = find(bcj[fd]);
}
int main() {
    //freopen("yl.out", " w ", stdout);
    //freopen("1.in", " r ", stdin);
    long long int n;
    cin >> n;
    bcj[1] = 1;
    bcjh[1] = 0;
    xb[1] = 1;
    while (n--)
    {
        string s1;
        cin >> s1;
        if (s1 == "add")
        {
            long long int x, y;
            string xba,xbb;
            cin >> x >> y>>xba>>xbb;
            if (bcj.find(x)==bcj.end())
            {
                bcj[x] = x;
                if (xba == "M")
                {
                    xb[x] = 0;
                    bcjh[x] = 0;
                }
                else
                {
                    xb[x] = 1;
                    bcjh[x] = 1;
                }
            }
            if (bcj.find(y)==bcj.end())
            {
                bcj[y] = y;
                bcjh[y] = 1;
                if (xbb == "M")
                {
                    xb[y] = 0;
                    bcjh[y] = 0;
                }
                else
                {
                    xb[y] = 1;
                    bcjh[y] = 1;
                }
            }
            long long int fa=find(x), fb=find(y);
            if (fa != fb)
            {
                bcj[fb] = fa;
                bcjh[fa] += bcjh[fb];
            }
        }
        else if (s1 == "query")
        {
            long long int x;
            cin >> x;
            if (bcj.find(x) == bcj.end())
            {
                cout << "NO"<<endl;
                continue;
            }
            long long int fa = find(x), fb = find(1);
            if (fa == fb&&xb[x]==1&&x!=1)
            {
                cout << "YES"<<endl;
            }
            else
            {
                cout << "NO"<<endl;
            }
        }
        else {
            cout << bcjh[find(1)]<<endl;
        }
    }
}

H
省略
I
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
int main(){
    cin.tie(nullptr)->ios::sync_with_stdio(false);
    int n;cin>>n;
    vector<int> s(n+2);
    for(int i=1;i<=n;i++)
        cin>>s[i];
    vector<int> v;
    for(int i=1;i<=n;i++)
        v.push_back(s[i]);
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    function<int(int)>find=[&](int x)->int{
        return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
    };
    vector<vector<int>> node(n+1); 
    for(int i=1;i<=n;i++)
        s[i]=find(s[i]);
    for(int i=1;i<=n;i++)
        node[s[i]].push_back(i);
    function<bool(int)> check=[&](int x)->bool{
        vector<int> L(n+1);
        vector<int> cnt(n+1);
        vector<int> R(n+1);
        for(int i=1;i<=n;i++){
            cnt[s[i]]++;
            if(cnt[s[i]]==x)L[s[i]]=i;
        }
        for(int i=1;i<=n;i++)
            cnt[i]=0;
        for(int i=n;i;i--){
            cnt[s[i]]++;
            if(cnt[s[i]]==x)R[s[i]]=i;
        }
        vector<vector<PII>> ne(n+1,vector<PII>(2));
        for(int i=1;i<=n;i++)
            if(L[i]<R[i]){
                if(R[i]>ne[L[i]][0].first)
                    ne[L[i]][0]={R[i],i};
                if(ne[L[i]][0].first>ne[L[i]][1].first)
                    swap(ne[L[i]][0],ne[L[i]][1]);
            }
        for(int i=1;i<=n;i++){
            if(ne[i-1][1]>ne[i][0]){
                ne[i][0]=ne[i-1][1];
                if(ne[i][0]>ne[i][1])
                    swap(ne[i][0],ne[i][1]);
                if(ne[i-1][0]>ne[i][0])
                    ne[i][0]=ne[i-1][0];
            }
        }
        for(int i=1;i<=n;i++)
            if(node[i].size()>=x){
                for(int j=0;j+x-1<node[i].size();j++){
                    int a=node[i][j],b=node[i][j+x-1];
                    if(ne[a-1][0].first>b && ne[a-1][0].second!=i)return true;
                    if(ne[a-1][1].first>b && ne[a-1][1].second!=i)return true;
                }
            }
        return false;
    };
    int l=1,r=n;
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid))l=mid+1;
        else r=mid-1;
    }
    if(r<=0)cout<<"-1";
    else cout<<n-3*r<<"\n";
}



2条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐