头像

Sufferingcreatinglife




离线:48分钟前


最近来访(46)
用户头像
WangJY
用户头像
acwing_4510
用户头像
章瑞涛
用户头像
77777777777
用户头像
大雪莱
用户头像
815741912
用户头像
tianen
用户头像
fangy
用户头像
trudbot
用户头像
AcWing2AK
用户头像
栗子ing
用户头像
琉璃_1
用户头像
Pluto1029
用户头像
ech0_7
用户头像
dugn2119
用户头像
龙骑士
用户头像
Eric.
用户头像
tuffynibbles
用户头像
cht
用户头像
007_4

活动打卡代码 AcWing 3428. 放苹果

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n,m;
int res,ans;

void dfs(int k,int x)
{
    if(k == n)
    {
        if(m - x >= ans) res ++ ;
        return ;
    }

    for (int i = x; i <= m; i ++ )
    {
        if(ans + i >= m) return;
        ans += i;
        dfs(k + 1,i);
        ans -= i;
    }
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    while(cin >> m >> n)
    {
        ans = res = 0;
        dfs(1,0);
        cout << res << endl;
    }
    return 0;
}



#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e6 + 10;
LL s[N];
int stk[N];
int n;

int main()
{
    int x;
    int top = 0;
    int res = 0;
    cin >> n;

    for(int i = 1;i <= n;i ++ )
    {
        cin >> x;
        s[i] = s[i - 1] + x - 100;
    }

    stk[ ++ top] = 0;

    for(int i = 1;i <= n;i ++ )
    {
        if(s[i] < s[stk[top]]) stk[ ++ top] = i;
        else if(s[i] > s[stk[top]])
        {
            int l = 1,r = top;
            while(l < r)
            {
                int mid = l + r >> 1;
                if(s[stk[mid]] >= s[i]) l = mid + 1;
                else r = mid;
            }
            res = max(res,i - stk[r]);
        }
    }

    cout << res;
    return 0;

}


活动打卡代码 AcWing 4486. 数字操作

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

int n;
vector<int> a;

int main()
{
    cin >> n;
    int m = 0,res = 1;

    for(int i = 2;i * i <= n;i ++ )
    {
        if(n % i == 0)
        {
            int c = 0;
            while(n % i == 0) n /= i,c ++ ;
            res *= i;
            a.push_back(c);
            while(1 << m < c) m ++ ;
        }
    }

    if(n > 1) {res *= n;a.push_back(1);}



    for(auto x : a)
        if(x < 1 << m)
        {
            m ++ ;
            break;
        }

    cout << res << " " << m;
    return 0;
}


活动打卡代码 AcWing 693. 行程排序

思路,设立一个行程哈希表,一个左哈希表表示左边有到它的点,设立一个集合表示所有机场,遍历集合即可找出左边没有到它的机场为出发地,然后依次遍历行程哈希表,即可求出路径

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

unordered_map<string,int> l;
unordered_map<string,string> s;
unordered_set<string> se;

int t,n;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> t;
    int len = t;
    string x,y,start;

    while(t -- )
    {
        l.clear(),s.clear(),se.clear();
        cin >> n;
        while(n -- )
        {
            cin >> x >> y;
            l[y] ++ ; 
            s[x] = y;
            se.insert(x);
            se.insert(y);
        }

        for(auto & z : se)
            if(!l[z])
            {
                start = z;
                break;
            }

        cout << "Case #" << len - t << ": "; 
        while(s[start] != "")
        {
            cout << start << "-" << s[start];
            if(s[start] != "") cout << " ";
            start = s[start];
        }
        if(t != 0) cout << endl;
    }

    return 0;
}



思路,设立一个行程哈希表,一个左哈希表表示左边有到它的点,设立一个集合表示所有机场,遍历集合即可找出左边没有到它的机场为出发地,然后依次遍历行程哈希表,即可求出路径

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

unordered_map<string,int> l;
unordered_map<string,string> s;
unordered_set<string> se;

int t,n;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> t;
    int len = t;
    string x,y,start;

    while(t -- )
    {
        l.clear(),s.clear(),se.clear();
        cin >> n;
        while(n -- )
        {
            cin >> x >> y;
            l[y] ++ ; 
            s[x] = y;
            se.insert(x);
            se.insert(y);
        }

        for(auto & z : se)
            if(!l[z])
            {
                start = z;
                break;
            }

        cout << "Case #" << len - t << ": "; 
        while(s[start] != "")
        {
            cout << start << "-" << s[start];
            if(s[start] != "") cout << " ";
            start = s[start];
        }
        if(t != 0) cout << endl;
    }

    return 0;
}


活动打卡代码 AcWing 4306. 序列处理

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 3010;
int a[N],b[N * 2] = {0};
int n;

int main()
{
    int res = 0;
    cin >> n;
    for(int i = 0;i < n;i ++)  cin >> a[i],b[a[i]] = 1;

    sort(a,a + n);

    for(int i = 0;i < n - 1;i ++ )
        if(a[i + 1] == a[i])
        {

            for(int j = a[i + 1] + 1;j < n * 2;j ++ )
                if(!b[j])
                {
                    //cout << j << " " << a[i + 1] << endl;
                    b[j] = 1;
                    res += j - a[i + 1];
                    break;
                }
        }

    cout << res;
    return 0;
}



#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int a[N],b[N] = {0};
int n;

int main()
{
    string s;
    cin >> n;
    int c = 1,d = 1;
    b[1] = 1;

    while(d < n)
    {
        int e = d;
        d = c + d;
        c = e;
        b[d] = 1;
    }


    for(int i = 1;i <= n;i ++ )
        if(b[i]) s += string(1,'O');
        else s += string(1,'o');

    cout << s;
    return 0;
}


活动打卡代码 AcWing 3311. 最长算术

#include <iostream>

using namespace std;

const int N = 21e5 + 10;
int n,m;
int a[N];

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int res = 0,k,ans;
    cin >> n;
    int l = n;

    while(n -- )
    {
        res = 0;
        cin >> m;
        for(int i = 0;i < m;i ++ ) cin >> a[i];
        if(m == 1) printf("Case #%d: %d\n",l - n,1);
        else
        {
            ans = 2;
            k = a[1] - a[0];
            for(int i = 1;i < m - 1;i ++ )
                if(a[i + 1] - a[i] == k)
                    ans ++ ;
                else
                {
                    res = max(res,ans);
                    k = a[i + 1] - a[i];
                    ans = 2;
                }
            res = max(res,ans);
            printf("Case #%d: %d\n",l - n,res);
        }
    }

    return 0;
}



代码:

#include <iostream>

using namespace std;

const int N = 21e5 + 10;
int n,m;
int a[N];

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int res = 0,k,ans;
    cin >> n;
    int l = n;

    while(n -- )
    {
        res = 0;
        cin >> m;
        for(int i = 0;i < m;i ++ ) cin >> a[i];
        if(m == 1) printf("Case #%d: %d\n",l - n,1);
        else
        {
            ans = 2;
            k = a[1] - a[0];
            for(int i = 1;i < m - 1;i ++ )
                if(a[i + 1] - a[i] == k)
                    ans ++ ;
                else
                {
                    res = max(res,ans);
                    k = a[i + 1] - a[i];
                    ans = 2;
                }
            res = max(res,ans);
            printf("Case #%d: %d\n",l - n,res);
        }
    }

    return 0;
}


活动打卡代码 AcWing 691. 立方体IV

#include <iostream>
#include <queue>
#include <unordered_map>

#define l first
#define r second

using namespace std;

typedef pair<int,int> PII;
const int N = 1010;
int a[N][N];
queue<PII> q;
int n,s;

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int res,idx,ans,id;
    cin >> n;
    int k = 0;

    while(n -- )
    {
        unordered_map<int,PII> mp;
        int b[1000010] = {0};
        idx = 1;
        res = 0;
        id = 0;
        cin >> s;
        for(int i = 0;i < s;i ++ )
            for(int j = 0;j < s;j ++ )
            {
                cin >> a[i][j];
                mp[a[i][j]] = {i,j};
            }

        while(idx <= s * s)
        {
            int start = idx;
            ans = 0;
            q.push(mp[idx]);

            while(!q.empty())
            {
                PII x = q.front();
                int dx = x.l,dy = x.r;
                q.pop();
                ans ++ ;
                b[a[dx][dy]] = 1;
                idx = max(idx,a[dx][dy]);
                //if(i == 1 && j == 1) cout << dx << " " << dy << endl;
                //cout << s << endl;

                if(dx + 1 < s && !b[a[dx + 1][dy]] && (a[dx + 1][dy] == a[dx][dy] + 1)) 
                    q.push({dx + 1,dy});
                if(dx - 1 >= 0 && !b[a[dx - 1][dy]] && (a[dx - 1][dy] == a[dx][dy] + 1)) 
                    q.push({dx - 1,dy});
                if(dy + 1 < s && !b[a[dx][dy + 1]] && (a[dx][dy + 1] == a[dx][dy] + 1)) 
                    q.push({dx,dy + 1});
                if(dy - 1 >= 0 && !b[a[dx][dy - 1]] && (a[dx][dy - 1] == a[dx][dy] + 1)) 
                    q.push({dx,dy - 1});
            }
            if(ans > res)
                {
                    res = ans;
                    id = start;
                }
            idx += 1;
        }

        printf("Case #%d: %d %d\n",++ k,id,res);
    }

    return 0;
}