头像

iltonmi

NEU-China




离线:3小时前



iltonmi
4天前

模拟

$O(12 * n)$

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

int cnt[8];

int main() {
    int n;
    cin >> n;
    // 当前月的第一天,是1900年以来的第k天,用来判断一周中的第几天
    int k = 1;
    memset(cnt, 0, sizeof cnt);
    // 遍历每年
    for(int i = 0; i < n; i++)
        // 遍历每个月
        for(int j = 1; j <= 12; j++) {
            // 计算出当前月的第13天是星期几
            int day = (12 + k) % 7;
            cnt[day ? day : 7]++;
            // 下面的逻辑,更新k成为下一个月的第一天
            if(j == 4 || j == 6 || j == 9 || j == 11) k += 30;
            else if(j == 2) {
                int year = 1900 + i;
                if((year % 400) == 0) k += 29;
                else if((year % 4) == 0 && year % 100) k += 29;
                else k += 28;
            } else k += 31;
        }
    for(int i = 6; i < 6 + 7; i++) cout << cnt[i % 7 ? i % 7 : 7] << ' ';
    puts("");
    return 0;
}



活动打卡代码 AcWing 1341. 十三号星期五

iltonmi
4天前
#include <iostream>
#include <cstring>

using namespace std;

int cnt[8];

int main() {
    int n;
    cin >> n;
    int k = 1;
    memset(cnt, 0, sizeof cnt);
    for(int i = 0; i < n; i++)
        for(int j = 1; j <= 12; j++) {
            int day = (12 + k) % 7;
            cnt[day ? day : 7]++;
            if(j == 4 || j == 6 || j == 9 || j == 11) k += 30;
            else if(j == 2) {
                int year = 1900 + i;
                if((year % 400) == 0) k += 29;
                else if((year % 4) == 0 && year % 100) k += 29;
                else k += 28;
            } else k += 31;
        }
    for(int i = 6; i < 6 + 7; i++) cout << cnt[i % 7 ? i % 7 : 7] << ' ';
    puts("");
    return 0;
}



iltonmi
5天前

模拟

$O(N^2P^2)$

C++ 代码

#include <iostream>
#include <unordered_map>

using namespace std;

typedef pair<int, int> PII;

unordered_map<string, PII> map;
unordered_map<string, int> income;

int main() {
    int n;
    cin >> n;
    string names[n];
    for(int i = 0; i < n; i++) cin >> names[i], income[names[i]] = 0;
    for(int i = 0; i < n; i++) {
        string name;
        int money, k;
        cin >> name >> money >> k;
        map[name] = {money, k};
        for(int j = 0; j < k; j++) {
            string to;
            cin >> to;
            income[to] += money / k;
        }
    }
    for(int i = 0; i < n; i++) {
        string name = names[i];
        int money = map[name].first, k = map[name].second;
        int res;
        if(k) res = money % k + income[name] - money;
        else res = money + income[name];
        cout << name << ' ' << res << endl;
    }
    return 0;
}


活动打卡代码 AcWing 1340. 贪婪的送礼者

iltonmi
5天前
#include <iostream>
#include <unordered_map>

using namespace std;

typedef pair<int, int> PII;

unordered_map<string, PII> map;
unordered_map<string, int> income;

int main() {
    int n;
    cin >> n;
    string names[n];
    for(int i = 0; i < n; i++) cin >> names[i], income[names[i]] = 0;
    for(int i = 0; i < n; i++) {
        string name;
        int money, k;
        cin >> name >> money >> k;
        map[name] = {money, k};
        for(int j = 0; j < k; j++) {
            string to;
            cin >> to;
            income[to] += money / k;
        }
    }
    for(int i = 0; i < n; i++) {
        string name = names[i];
        int money = map[name].first, k = map[name].second;
        int res;
        if(k) res = money % k + income[name] - money;
        else res = money + income[name];
        cout << name << ' ' << res << endl;
    }
    return 0;
}



iltonmi
5天前
#include <iostream>

using namespace std;

const int mod = 47;

int trans(string& s)
{
    int res = 1;
    for(auto& c : s) res *= 1 + (c - 'A');
    return res % mod;
}

int main()
{
    string a, b;
    cin >> a >> b;
    if(trans(a) == trans(b)) puts("GO");
    else puts("STAY");
    return 0;
}



iltonmi
7天前

前缀和+后缀和数组(有兴趣可以自己用前缀和算出后缀和,则只需要一个数组)

时间复杂度 $O(n)$

// 以被删除元素为分界点,前面的奇偶不变,后面元素位置的奇偶颠倒
// first:和被删除元素位置奇偶相同的元素和
// 由2部分组成:
// 1. pre[i + 1] - val,是被删除元素前面,位置奇偶性相同元素的前缀和
// 2. suf[i + 1],是被删除元素后面,和被删除元素奇偶性相反元素的后缀和,删除元素后,由于奇偶性颠倒
// 和被删元素奇偶性相同
// second:和被删除元素位置奇偶性相反的元素和
// 由2部分组成:
// 1. pre[i],被删元素前一个元素所在序列的前缀和
// 2. suf[i] - val,是被删除元素后面,和被删除元素奇偶性相同元素的后缀和,删除元素后,由于奇偶性颠倒
// 和被删元素奇偶性恰好相反

C++ 代码 (奇偶数组版)

class Solution {
public:
    int waysToMakeFair(vector<int>& nums) {
        int len = nums.size();
        int pre[len + 1], suf[len + 1];
        pre[0] = 0, suf[len] = 0;
        for(int i = 1; i <= len; i++)
            pre[i] = nums[i - 1] + (i - 2 >= 0 ? pre[i - 2] : 0);
        for(int i = len - 1; i >= 0; i--)
            suf[i] = nums[i] + (i + 2 <= len ? suf[i + 2] : 0);
        int cnt = 0;
        for(int i = 0; i < len; i++)
        {
            int val = nums[i];
            int first = pre[i + 1] - val + suf[i + 1];
            int second = pre[i] + suf[i] - val;
            if(first == second) cnt++;
        }
        return cnt;
    }
};

C++代码(单数组版,emmm比开2个数组复杂。。。)

class Solution {
public:
    // 前面的奇偶不变,后面的奇偶替换
    int waysToMakeFair(vector<int>& nums) {
        int len = nums.size();
        int pre[len + 1];
        pre[0] = 0;
        for(int i = 1; i <= len; i++)
            pre[i] = nums[i - 1] + (i - 2 >= 0 ? pre[i - 2] : 0);
        int cnt = 0;
        for(int i = 0; i < len; i++)
        {
            int val = nums[i];
            int end = (len - 1 - i) & 1 ? len - 2 : len - 1;
            // 不同的末尾
            int first = pre[i + 1] - val + pre[(len - 1 - i) & 1 ? end + 2 : end] - pre[i];
            // 相同的末尾
            int second = pre[i] + pre[end + 1] - pre[i + 1];
            if(first == second) cnt++;
        }
        return cnt;
    }
};



iltonmi
8天前
class Solution {
public:
    // 以被删除元素为分界点,前面的奇偶不变,后面元素位置的奇偶颠倒
    // first:和被删除元素位置奇偶相同的元素和
    // 由2部分组成:
    // 1. pre[i + 1] - val,是被删除元素前面,位置奇偶性相同元素的前缀和
    // 2. suf[i + 1],是被删除元素后面,和被删除元素奇偶性相反元素的后缀和,删除元素后,由于奇偶性颠倒
    // 和被删元素奇偶性相同
    // second:和被删除元素位置奇偶性相反的元素和
    // 由2部分组成:
    // 1. pre[i],被删元素前一个元素所在序列的前缀和
    // 2. suf[i] - val,是被删除元素后面,和被删除元素奇偶性相同元素的后缀和,删除元素后,由于奇偶性颠倒
    // 和被删元素奇偶性恰好相反
    int waysToMakeFair(vector<int>& nums) {
        int len = nums.size();
        int pre[len + 1], suf[len + 1];
        pre[0] = 0, suf[len] = 0;
        for(int i = 1; i <= len; i++)
            pre[i] = nums[i - 1] + (i - 2 >= 0 ? pre[i - 2] : 0);
        for(int i = len - 1; i >= 0; i--)
            suf[i] = nums[i] + (i + 2 <= len ? suf[i + 2] : 0);
        int cnt = 0;
        for(int i = 0; i < len; i++)
        {
            int val = nums[i];
            int first = pre[i + 1] - val + suf[i + 1];
            int second = pre[i] + suf[i] - val;
            if(first == second) cnt++;
        }
        return cnt;
    }
};



iltonmi
8天前
class Solution {
public:
    string res;
    string getSmallestString(int n, int k) {
        int cur = 26 * n;
        int ci = 0;
        for(int i = 0; i < n; i++)
        {
            while(cur - 26 + ci + 1 < k) ci++;
            res += 'a' + ci;
            cur = cur - 26 + ci + 1;
        }
        return res;
    }
};



iltonmi
8天前
class Solution {
public:
    bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
        for(int i1 = 0, i2 = 0, j1 = 0, j2 = 0; i1 < word1.size() && i2 < word2.size();)
        {
            // cout << word1[i1][j1] << ' ' << word2[i2][j2] << endl;
            if(word1[i1][j1] != word2[i2][j2]) return false;
            if(j1 == word1[i1].size() - 1) j1 = 0, i1++;
            else j1++;
            if(j2 == word2[i2].size() - 1) j2 = 0, i2++;
            else j2++;
        }
        return true;
    }
};



iltonmi
16天前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        if(head == NULL) return NULL;
        ListNode* slow = head;
        ListNode* fast = head->next;
        while(slow != fast) {
            if(fast == NULL || fast->next == NULL) return NULL;
            slow = slow->next, fast = fast->next->next;
        }
        ListNode* dummy = new ListNode(-1);
        dummy->next = head, slow = dummy;
        while(slow != fast) slow = slow->next, fast = fast->next;
        return slow;
    }
};