头像

Auto




离线:2小时前


活动打卡代码 AcWing 3491. 完全平方数

Auto
3天前
#include <iostream>
#include <vector>

using namespace std;

typedef long long LL;

/*

n = p1 ^ k1 + p2 ^ k2 + ... pm ^ km

2^9 * 3^1
512*3
1536

*/


int main()
{
    LL n;
    cin >> n;
    vector<pair<LL,int>>vec;
    for(LL i = 2;i * i <= n;i ++){
        if(n % i == 0){
            int cnt = 0;
            while(n && n % i == 0){
                n = n / i;
                cnt ++;
            }
            vec.push_back({i,cnt});
        }
    }

    if(n != 1){

        vec.push_back({n,1});
    }
    LL ans = 1;
    for(auto &x : vec){
        if(x.second % 2 == 0) continue;
        ans = ans * x.first;
    }
    cout << ans << endl;

    return 0;
}


活动打卡代码 AcWing 3490. 小平方

Auto
3天前
#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int cnt = 0;
    for(int i = 1;i < n;i ++){
        if(i * i % n < (n + 1) / 2){
            cnt ++;
        }
    }

    cout << cnt << endl;

    return 0;
}


活动打卡代码 AcWing 3496. 特殊年份

Auto
3天前
#include <iostream>
using namespace std;

int main()
{
    int cnt = 0;
    for(int i = 0;i < 5;i ++)
    {
        int x;
        cin >> x;
        int a = x % 10;
        x = x / 10;
        int b = x % 10;
        x = x / 10;
        int c = x % 10;
        int d = x / 10;


        if(d == b && a - c == 1) cnt ++;
    }

    cout << cnt << endl;

    return 0;
}



Auto
19天前
class Solution {
public:
    int maxIceCream(vector<int>& costs, int coins) {
        sort(costs.begin(),costs.end());
        int cnt = 0;
        for(auto &x : costs){
            if(coins >= x){
                cnt ++;
                coins -= x;
            }else{
                break;
            }
        }
        return cnt;
    }
};



Auto
19天前
class Solution {
public:
    bool checkIfPangram(string sentence) {
        set<int>st;
        for(auto &x : sentence){
            st.insert(x);
        }
        return st.size() == 26;
    }
};


活动打卡代码 AcWing 3416. 时间显示

Auto
20天前
#include <bits/stdc++.h>
using namespace std;

int main()
{
    long long t;
    cin >> t;
    t = t / 1000;
    t = t % (24 * 60 * 60);
    int h,m,s;
    h = t / 3600;
    t = t % 3600;
    m = t / 60;
    t = t % 60;
    s = t;
    printf("%02d:%02d:%02d\n",h,m,s);

    return 0;
}



Auto
20天前
class Solution {
public:
    int longestBeautifulSubstring(string word) {
        int ans = 0;
        int cnt = 0;
        map<char,int>mp;
        mp['a'] = 1;
        mp['e'] = 2;
        mp['i'] = 3;
        mp['o'] = 4;
        mp['u'] = 5;
        mp['z'] = 100;
        for(int i = 0;i < word.size();i ++){
            if(word[i] != 'a'){
                cnt ++;
            }else{
                break;
            }
        }
        word += 'z';

        for(int i = cnt;i < word.size() - 1;i ++){
            char a = word[i + 1];
            char b = word[i];
            int c = mp[a] - mp[b];
            if(cnt == 0 && b != 'a') continue;
            if(c == 0 || c == 1){
                cnt ++;
            }else{
                if(cnt != 0)
                    cnt ++;
                if(b == 'u'){
                    ans = max(ans,cnt);
                }
                cnt = 0;
            }
           // cout << cnt << endl;
        }
        return ans;
    }

};



Auto
20天前

const int N = 1e6 + 10;
long long sum[N];
int n;
class Solution {
public:

    bool check(int mid,int k)
    {
        for(int i = mid;i <= n;i ++){
            long long a = sum[i] - sum[i - 1];

            if(a * (mid) - (sum[i] - sum[i - mid]) <= k){
                return true;
            }
        }
        return false;
    }

    int maxFrequency(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        n = nums.size();
        int l = 0,r = nums.size();
        sum[0] = 0;
        for(int i = 1;i <= n;i ++){
            sum[i] = sum[i - 1] + nums[i - 1];
        }

        while(l < r){
            int mid = l + r + 1 >> 1;
            if(check(mid,k)){
                l = mid;
            }else{
                r = mid - 1;
            }
        }
        return l;
    }
};



Auto
20天前
class Solution {
public:
    int sumBase(int n, int k) {    
        int sum = 0;
        while(n){
            sum += n % k;
            n = n / k;
        }
        return sum;
    }
};



Auto
22天前
  • L1-1
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec[N];
int k;
int ans[N];

int main()
{
    cout << "To iterate is human, to recurse divine.";

    return 0;
}
  • L1-2

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec[N];
int k;
int ans[N];

int main()
{
    cin >> n >> m >> k;
    cout << n - m * k << endl;

    return 0;
}
  • L1-3
// 这个题有个坑点,也不算是坑点吧,题目给的是6位或者4位,我直接认为给了4位开始。


#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec[N];
int k;
int ans[N];

int main()
{
    string str;
    cin >> str;

    if(str.size() == 4){
        int f1 = (str[0] - '0') * 10 + str[1] - '0';
        if(f1 < 22){
            printf("20%02d-%c%c",f1,str[2],str[3]);
        }else{
            cout << 19 << f1 << '-' << str[2]  << str[3] << endl;
        }
    }else{
        string s1;
        s1 += str[0];
        s1 += str[1];
        s1 += str[2];
        s1 += str[3];
        cout << s1 << '-' << str[4] << str[5] << endl;
    }



    return 0;
}
  • L1-4
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec[N];
int k;
int ans[N];

int main()
{
    int n,m;
    cin >> n >> m;
    double p;
    while(n --){
        double x;
        cin >> x;
        if(x < m){
            printf("On Sale! %.1lf\n",x);
        }
    }


    return 0;
}
  • L1-5
// 有个坑点就是超出了范围,题目里面明确说了,希望这个地方注意一下
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec[N];
int k;
int ans[N];

int main()
{
    for(int i = 0;i < 24;i ++){
        cin >> ans[i];
    }
    int x;
    while(cin >> x && x != -1){
        if(x >= 24 || x < 0) break;
        if(ans[x] > 50){
            printf("%d Yes\n",ans[x]);
        }else{
            printf("%d No\n",ans[x]);
        }
    }


    return 0;
}
  • L1-6
// 我当时没有getchar(),找了好长时间的bug
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<string>vec;
int k;
int ans[N];

int main()
{
    vec.clear();
    cin >> n >> k;
    getchar();
    for(int i = 0;i < n;i ++){
        string str;

        getline(cin,str);
        if(str.find("easy") != -1) continue;
        if(str.find("qiandao")!= -1) continue;
        vec.push_back(str);
    }


    if(k >= vec.size()) cout << "Wo AK le" << endl;
    else
    cout << vec[k] << endl;

    return 0;
}
  • L1-7
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec;
int k;
int ans[N];

int main()
{
    int n;
    cin >> n;
    for(int i = 0,x;i < n;i ++){
        cin >> x;
        vec.push_back(x);
    }

    sort(vec.begin(),vec.end());

    int f1 = vec[0],f2 = vec[vec.size() - 1];
    int cnt = 0;
    for(auto &x : vec){
        if(x == f1){
            cnt ++;
        }
    }
    cout << f1 << ' ' << cnt << endl;
    cnt = 0;
    for(auto &x : vec){
        if(x == f2){
            cnt ++;
        }
    }

    cout << f2 << ' ' << cnt << endl;

    return 0;
}

  • L1-8
// 这个直接模拟就好了,有个点就是 >= 10,我当时写成了 > 10,差一分满分,不过立刻找出来了这个错误
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec;
int k;
int ans[N];

int main()
{
    int a,b,c;
    cin >> a >> b >> c;

    vec.push_back(a);
    vec.push_back(b);
    int f1 = 0,f2 = 1;
    while(vec.size() < c + 100){
        int f3 = vec[f1] * vec[f2];
    //  cout << f3<< endl;

        if(f3 >= 10){
            vec.push_back(f3 / 10);
            vec.push_back(f3 % 10);
        }
        else{
            vec.push_back(f3);
        }
        f1 ++;
        f2 ++;
    }

    for(int i = 0;i < c;i ++){
        if(i == c - 1){
            cout << vec[i];
        }else{
            cout << vec[i] << ' ';
        }
    }

    return 0;
}
  • L2-1
// 我个人觉得题意有点问题,也可能是我的阅读理解不太好,就是如果栈满了话,并且此时操作的那个序列已经到头了,这视为一种无用的操作,而不是把栈顶元素放入到答案中
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m,k;
vector<pair<string,int>>vec;

int main()
{
    cin >> n >> m >> k;   
    string str;
    vec.push_back({"",0});
    for(int i = 0;i < n;i ++){
        cin >> str;
        vec.push_back({str,0});
    }

    string ans;
    int op;
    stack<char>stk;
    while(cin >> op && op != -1){

        int id1 = vec[op].second;
        if(id1 >= m) continue;
        if(stk.size() == 0 && op == 0) continue;
        if(op != 0 && stk.size() >= k){
            ans += stk.top();
            stk.pop();
        }

        if(op == 0){

            ans += stk.top();
            stk.pop();
        }else{

            int id = vec[op].second;
            if(id >= m) continue;
            stk.push(vec[op].first[id]);
            vec[op].second ++;
        }

    }
    cout << ans << endl;

    return 0;
}
/*
3 4 100
GPLT
PATA
OMSA
3 2 3 0 1 2 0 2 2 0 -1

*/
  • L2-2
// 那个字典序最小的串,有点难到我了,于是就先放了一下,先做L2-3,然后L2-310分钟左右写完了,就发现这俩好像一模两样,把所有的答案记录下来,然后按照L2-3的那个排序排个序就好了
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec[N];
int din[N];

int dist[N];
int pre[N];
int ans = 0;
vector<int>v;

void dfs(int p)
{
    for(auto &x : vec[p]){
        if(dist[x] <= dist[p] + 1){
            dist[x] = dist[p] + 1;  
            pre[x] = p;
        }

        if(dist[x] > dist[ans]){
            ans = x;
        }
        else if(dist[x] == dist[ans]){
            if(x < ans){
                ans = x;
            }
        }
        dfs(x);
    }
}

vector<int> ans1;

void dfs1(int p)
{
    ans1.push_back(p);
    if(pre[p] == -1) return;
    dfs1(pre[p]);
}

int main()
{
    memset(pre,-1,sizeof(pre));

    cin >> n;
    for(int i = 0;i < n;i ++){
        int k;
        cin >> k;
        while(k --){
            int x;
            cin >> x;
            vec[i].push_back(x);
            din[x] ++;
        }
    }
    int root;
    for(int i = 0;i < n;i ++){
        if(din[i] == 0){
            root = i;
            break;
        }
    }

    ans = root;
    dist[root] = 1;

    dfs(root);
    vector<vector<int>>v1;
    for(int i = 0;i < n;i ++){
        if(dist[i] == dist[ans]){
            v.push_back(i);
            dfs1(i);
            reverse(ans1.begin(),ans1.end());
            v1.push_back(ans1);
            ans1.clear();
        }
    }

    cout << dist[ans] << endl;

    sort(v1.begin(),v1.end(),[](vector<int>p1,vector<int>p2){
        int n1 = p1.size();
        int n2 = p2.size();
        for(int i = 0;i < n1 && i < n2;i ++){
            if(p1[i] == p2[i]) continue;
            return p1[i] < p2[i];
        }

        return n1 < n2;

    });

    for(int i = 0;i < v1[0].size();i ++){
        if(i == v1[0].size() - 1){
            cout << v1[0][i];
        }else{
            cout << v1[0][i] << ' ';
        }
    }

    return 0;
}
  • L2-3
// 我同学第一维有用string的,我认为这是一个好的选择
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec[N];

map<vector<int>,int>mp;

vector<pair<vector<int>,int>>v;

int main()
{
    cin >> n >> m;
    for(int i = 0;i < n;i ++){
        for(int j = 0;j < m;j ++){
            int x;
            cin >> x;
            vec[i].push_back(x);
        }
        mp[vec[i]] ++;
    }

    for(auto &x : mp){
        v.push_back({x.first,x.second});
    }

    sort(v.begin(),v.end(),[](pair<vector<int>,int> p1,pair<vector<int>,int> p2){

        if(p1.second == p2.second){
            for(int i = 0;i < p1.first.size();i ++){
                if(p1.first[i] == p2.first[i]) continue;
                return p1.first[i] < p2.first[i];
            }
        }
        return p1.second > p2.second;
    });
    cout << v.size() << endl;

    for(auto &x : v){
        cout << x.second;

        for(auto &y : x.first){
            cout << ' ' << y;
        }
        cout << endl;
    }


    return 0;
}

  • L2-4
// 最开始做的这个题,我当时以为我是第一个A掉的,原来是我想多了。
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n,m;
vector<int>vec[N];
int k;
int ans[N];

int main()
{
    cin >> n >> m;

    for(int i = 1;i <= n;i ++){
        vec[i].push_back(0);
    }

    for(int i = 1;i <= n;i ++){
        cin >> k;
        for(int j = 0,x;j < k;j ++){
            cin >> x;
            vec[i].push_back(x);
        }
    }
    int s = 1,cnt = 1;
    for(int i = 1;i <= m;i ++){
        int op,w;
        cin >> op >> w;
        if(op == 0){
            s = vec[s][w];
        }else if(op == 1){
            ans[w] = s;
            cout << s << endl;
            s = ans[w];

        }else if(op == 2){
            s = ans[w];
        }
    }
    cout << s << endl;

    return 0;
}
  • L3-1
  • 这个题好像是卡掉spfa,我超时了一个点,,用了对优化的dijkstra,就不超时了,
  • 还有一个点错的可能是n等于1的情况
  • 思路:计算1各个点的最短路,这个是记录花费现金到每个地方的最小花费
  • 再计算n到各个点的最短路,这个记录的是n号点用旅游金到每个点的最少花费
  • 路是单向的,不要弄错了。
  • 然后通过优先队列来找到目标答案
  • 注意一下我这里虽然写的spfa,但是实际用的对优化的dijkstra
  • 注意这个题如果不能到达的话,不能加入到答案的优先队列中
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,m,q;
const LL N = 1e6 + 10;
vector<pair<LL,pair<LL,LL>>>vec[N];
LL w[N];
const LL INF = 1e18;
bool st[N];
LL dist1[N];
LL dist2[N];

LL cost[N];

void spfa(LL *dist,LL op,LL s)
{
    memset(st,0,sizeof st);
    dist[s] = 0;

    priority_queue<pair<LL,LL>,vector<pair<LL,LL>>,greater<pair<LL,LL>>>heap;
    heap.push({0,s});

    while(heap.size())
    {
        auto tt = heap.top();
        LL t = tt.second;
        heap.pop();
        if(st[t]) continue;
        st[t] = false;
        for(auto &x : vec[t]){
            LL f1 = x.first;
            LL f2;
            if(op == 1){
                f2 = x.second.first;
            }
            else{
                f2 = x.second.second;
            }
            if(dist[f1] > dist[t] + f2){
                dist[f1] = dist[t] + f2;
                    heap.push({dist[f1],f1});
            }
        }
    }
}


int main()
{
    cin >> n >> m >> q;

    for(LL i = 0;i < m;i ++){
        LL a,b,c,d;
        cin >> a >> b >> c >> d;
        if(a == b) continue;
        vec[a].push_back({b,{c,INF}});
        vec[b].push_back({a,{INF,d}});
    }

    for(LL i = 1;i <= n;i ++){
        cin >> w[i];
        dist1[i] = INF;
        dist2[i] = INF;
    }

    spfa(dist1,1,1);
    spfa(dist2,2,n);

    LL sum = INF;
    LL s;

    priority_queue<pair<LL,LL>,vector<pair<LL,LL>>,greater<pair<LL,LL>>>heap;

    for(LL i = 1;i <= n;i ++){
        if(dist1[i] == INF || dist2[i] == INF) continue;
        cost[i] = dist1[i] + (dist2[i] + w[i] - 1) / w[i];
        heap.push({cost[i],i});
    }
    sum = heap.top().first;
    while(q --)
    {
        LL a,b;
        cin >> a >> b;
        w[a] = b;
        if(dist1[a] == INF || dist2[a] == INF){
            cout << sum << endl;
            continue;
        } 
        cost[a] = dist1[a] + (dist2[a] + w[a] - 1) / w[a];
        heap.push({cost[a],a});

        while(heap.size())
        {
            auto t = heap.top();
            LL f1 = t.first,f2 = t.second;
            if(f1 < cost[f2]){
                heap.pop();
            }
            else{
                sum = f1;
                break;
            }
        }

        cout << sum << endl;
    }

    return 0;
}
  • L3-2
// 官方题解好像是KMP,但是我建了一个图,然后爆搜了一下,就过了
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int n;
int a[N];
int k;
vector<int>vec[N];

int g[110][110];
vector<int>ans;

bool st[N];

bool dfs(int p,int s)
{

    int l1 = vec[p].size();
//  cout << p << ' ' << l1 << endl;

    for(int i = 0;i < l1;i ++){
        int i1 = s + i,i2 = i;
    //  cout << a[i1] << ' ' << vec[p][i2] << endl;
        if(a[i1] != vec[p][i2]){
            return false;
        }
    }

    if(s + l1 - 1 == n) {
        return true;    
    }

    for(int i = 1;i <= k;i ++){
        if(st[i]) continue;
        if(g[p][i]){
            st[i] = true;
            ans.push_back(i);
            if(dfs(i,s + l1 - 1)){
                return true;
            }
            ans.pop_back();

            st[i] = false;
        }
    }
    return false;
}

int main()
{

    cin >> n;
    for(int i = 1;i <= n;i ++)
        cin >> a[i];

    cin >> k;
    for(int i = 1;i <= k;i ++){
        int m;
        cin >> m;
        while(m --){
            int x;
            cin >> x;
            vec[i].push_back(x);
        }
    }

    unordered_set<int>stt;

    for(int i = 1;i <= k;i ++){
        int ed = vec[i][vec[i].size() - 1];
        for(int j = 1;j <= k;j ++){
            int f1 = vec[j][0];
            if(ed == f1){
                g[i][j] = 1;
            }
            if(f1 == a[1]){
                stt.insert(j);
            }
        }
    }

    for(auto &x : stt){
        ans.push_back(x);
        st[x] = true;
        if(dfs(x,1)){
            break;
        }
        st[x] = false;
        ans.clear();
    }

    for(int i = 0;i < ans.size();i ++){
        if(i == ans.size() - 1){
            cout << ans[i];
        }else{
            cout << ans[i] << ' ';
        }
    }

    return 0;
}