头像

clearmann

安阳工学院




离线:11小时前


最近来访(97)
用户头像
是风.
用户头像
小妹妹送我的郎啊
用户头像
lindi530
用户头像
323
用户头像
Q_15
用户头像
人生如戏ba
用户头像
叫我十八
用户头像
执念成狂@
用户头像
jzz2002
用户头像
TKater_yzt
用户头像
ShanLin
用户头像
zhyou
用户头像
小zz
用户头像
кун
用户头像
一万小时定律
用户头像
寒暄a
用户头像
听雨.
用户头像
lixiangsanxun
用户头像
海_43
用户头像
一只野生の彩色铅笔


clearmann
15小时前
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int n, m, k;
int dist[N], back_up[N];
struct Node
{
    int a, b, c;
}edges[N];
void bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int i = 1; i <= k; i ++)
    {
        memcpy(back_up, dist, sizeof dist);
        for(int j = 1; j <= m; j ++)
        {
            auto t = edges[j];
            dist[t.b] = min(dist[t.b], back_up[t.a] + t.c);
        }
    }
}
int main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i ++)
        cin >> edges[i].a >> edges[i].b >> edges[i].c;
    bellman_ford();
    if(dist[n] > 0x3f3f3f3f / 2)    cout << "impossible" << endl;
    else cout << dist[n] << endl;
    return 0;
}



浅写一下调和级数的题解

题目描述

Supervin是一名图书管理员,有一本共 N 页,页码编号为 1 ~ N 的古书由他管理。

由于书太破旧了,因此其中的 M 页处于残缺状态,这 M 页的编号分别是 P1,P2,…,PM。

现在,有 Q 名十分懒惰的读者对阅读这本书产生了兴趣。

因为他们很懒惰,因此他们并不打算将书整本阅读。

现在已知第 i 名读者将会阅读所有页面编号能被 Ri 整除且没有残缺的书页。

Supervin想知道所有读者的实际阅读页数相加的和为多少。

输入格式

第一行包含整数 T,表示共有 T 组测试数据。

每组数据占三行,其中第一行包含三个整数 N,M,Q,分别表示书的总页数,残缺页数以及读者数。

第二行包含 M 个整数,其中第 i 个数为 Pi。

第三行包含 Q 个整数,其中第 i 个数为 Ri。

输出格式

每组数据输出一个结果,每个结果占一行。

结果表示为“Case #x: y”,其中x是组别编号(从1开始),y为所有读者的实际阅读页数相加的和。

数据范围

1≤T≤100,
1≤P1<P2<…<PM≤N,
1≤Ri≤N,
1≤M≤N≤105
1≤Q≤105

输入样例:

3
11 1 2
8
2 3
11 11 11
1 2 3 4 5 6 7 8 9 10 11
1 2 3 4 5 6 7 8 9 10 11
1000 6 1
4 8 15 16 23 42
1

输出样例:

Case #1: 7
Case #2: 0
Case #3: 994

时间复杂度 $O(n * ln(n))$

思路:寻找多个数的倍数时,可以选择调和级数 这种枚举方法

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, q, tot[N], res, k;
int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        k ++;
        res = 0;
        cin >> n >> m >> q;
        memset(tot, 0, sizeof tot);//多组数据,让tot归零
        int x;
        for(int i = 1; i <= m; i ++)    cin >> x, tot[x] ++;//将每个出现的数字记录一下
        while(q --)
        {
            int t;
            cin >> t;
            for(int i = t; i <= n; i += t) //依次枚举t的倍数
                if(tot[i] == 0) res++;
        }
        cout << "Case #" << k << ": " << res << endl;
    }
    return 0;
}



浅写一点自己犯的sb错误
1. 线段树query和modify一定要写pushup和pushdown
2. 题目一定注意边界条件!!!!把各种等于1等于n的情况考虑完
3. 一种情况如果难以想清楚分类把所有情况都找出来理清思路
4. 线段树update记得pushup,pushup的时候记得把所有标记都捡上来
5. 位运算各种骚操作关键时候有奇效
6. 下次打错文件名剁手!!!
7. 多组数据一定要记得清空啊qaq 链式前向星什么的再翻车就凉了
8. 数组不要开小了啊啊啊啊!!!
9. 能暴力过就最好不要优化, 鬼永远不知道会给你的代码加上什么可怕的负优化
10. 能按照题解要求解答的就直接暴力写,不要对题目乱增加自己的主观判断(n多次因为这个,简单题无限wa还不知道哪里错了)
11. 初始化的时候没有memset就一定要记得检查是否初始化完要用的值
12. 在使用位运算的时候 一定要加括号,记清位运算的优先级!!!无限次因为位运算 bug调不出来
13. 做题前带脑子 不要直接上 想清楚再写!!!
14. 难题不要弃疗,从最简单的部分想起,记得分析复杂度 (高中错误做题方法,十几二十几分钟想不出来,就直接下班)
15. 对于一个很大的数观察可能质因子会很少 设计与这个相关的算法会较优
16. 不要写题的时候写一些奇怪的操作…一定要按写过的能ac的方法写,dfs是先传递信息再往下搜!!!
17. 搜索的时候记得观察会不会死循环 不然考虑记忆化。



活动打卡代码 AcWing 4617. 解方程

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define debug(val)  \
    cout << #val << " = " << (val) << endl
#define Accept 0
const int N = 1e5+10;
int n;
void solve() {
    cin >> n;
    int cnt = 1;
    while(n)
    {
        if(n & 1)
            cnt = cnt * 2;;
        n = n >> 1;
    }
    cout << cnt << endl;
    return ;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return Accept;
}



活动打卡代码 AcWing 4616. 击中战舰

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define debug(val)  \
    cout << #val << " = " << (val) << endl
#define Accept 0
const int N = 2e5 + 10;
int n, a, b, k, cnt;
char s[N];
vector<int> q;
void solve() {
    scanf("%lld%lld%lld%lld", &n, &a, &b, &k);
    scanf("%s", s + 1);
    for(int i = 1, len = 0; i <= n; i ++)
    {
        if(s[i] == '0') len ++;
        else len = 0;
        if(len == b)
        {
            cnt ++;
            len = 0;
        }
    }
    for(int i = 1, len = 0; i <= n && cnt != a - 1; i ++)
    {
        if(s[i] == '0') len ++;
        else len = 0;
        if(len == b && cnt > a - 1)
        {
            q.push_back(i);
            len = 0;
            cnt --;
        }
    }
    cout << q.size() << endl;
    for(int i = 0; i < q.size(); i ++)   cout << q[i] << " ";
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
//  cin >> T;
    while (T--) {
        solve();
    }
    return Accept;
}



活动打卡代码 AcWing 4615. 相遇问题

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define debug(val)  \
    cout << #val << " = " << (val) << endl
#define Accept 0
const int N = 1e5+10;
void solve() {
    int x, y, a, b;
    cin >> x >> y >> a >> b;
    int t = y - x;
    if(t % (a + b) == 0)    cout << t / (a + b) << endl;
    else cout << -1 << endl;
    return ;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return Accept;
}



活动打卡代码 AcWing 1460. 我在哪?

clearmann
14天前
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define debug(val)  \
    cout << #val << " = " << (val) << endl
#define Accept 0
const int N = 110, P = 131, M = 1610612741;
char s[N];
int n, h[N], p[N];
int get(int l, int r)
{
    return (h[r] - h[l - 1] * p[r - l + 1] % M + M) % M;
}
void solve() {
    cin >> n;
    cin >> s + 1;
    p[0] = 1;
    for(int i = 1; i <= n; i ++)
    {
        h[i] = (h[i - 1] * P % M+ s[i]) % M;
        p[i] = p[i - 1] * P % M;
    }
    for(int len = 1; len <= n; len ++)
    {
        bool flag = false;
        for(int l1 = 1; l1 + len - 1 <= n; l1 ++)
        {
            int r1 = l1 + len - 1;
            for(int l2 = l1 + 1; l2 + len - 1 <= n; l2 ++)
            {
                int r2 = l2 + len - 1;
                if(get(l1, r1) == get(l2, r2)) flag = true;
                if(flag)    break;
            }
            if(flag)    break;
        }
        if(!flag) 
        {
            cout << len << endl;
            return ;
        }
    }
    return ;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
//  cin >> T;
    while (T--) {
        solve();
    }
    return Accept;
}



活动打卡代码 AcWing 841. 字符串哈希

clearmann
14天前
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define debug(val)  \
    cout << #val << " = " << (val) << endl
#define Accept 0
typedef unsigned long long ULL;
const int N = 1e5+10, P = 131;
int n, m;
ULL h[N], p[N];
char s[N];
ULL get(int l,int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}
void solve() {
    cin >> n >> m;
    cin >> (s + 1);
    p[0] = 1;
    for(int i = 1; i <= n; i ++)
    {
        h[i] = h[i - 1] * P + s[i];
        p[i] = p[i - 1] * P;
    }
    int a, b, c, d;
    while(m --)
    {
        cin >> a >> b >> c >> d;
        if(get(a, b) == get(c, d))  cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return ;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
//  cin >> T;
    while (T--) {
        solve();
    }
    return Accept;
}
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define debug(val)  \
    cout << #val << " = " << (val) << endl
#define Accept 0
typedef unsigned long long ULL;
const int N = 1e5+10, P = 131, M = 1610612741;
int n, m;
int h[N], p[N];
char s[N];
int get(int l,int r)
{
    return (h[r] - h[l - 1] * p[r - l + 1] % M + M) % M;
}
void solve() {
    cin >> n >> m;
    cin >> (s + 1);
    p[0] = 1;
    for(int i = 1; i <= n; i ++)
    {
        h[i] = (h[i - 1] * P + s[i]) % M;
        p[i] = p[i - 1] * P % M;
    }
    int a, b, c, d;
    while(m --)
    {
        cin >> a >> b >> c >> d;
        if(get(a, b) == get(c, d))  cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return ;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
//  cin >> T;
    while (T--) {
        solve();
    }
    return Accept;
}


活动打卡代码 AcWing 4613. 方格跳跃

clearmann
17天前
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define debug(val)  \
    cout << #val << " = " << (val) << endl
#define Accept 0
const int N = 1e5+10;
int n, res;
string s;
void solve() {
    cin >> n;
    cin >> s;
    for(int i = 0; i < s.size(); i ++)
    {
        if(s[i] == '<') res ++;
        else    break;
    }
    for(int i = s.size() - 1; i >= 0; i --)
    {
        if(s[i] == '>') res ++;
        else    break;
    }
    cout << res << endl;
    return ;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
//  cin >> T;
    while (T--) {
        solve();
    }
    return Accept;
}



活动打卡代码 AcWing 4612. 去掉0

clearmann
17天前
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define debug(val)  \
    cout << #val << " = " << (val) << endl
#define Accept 0
const int N = 1e5+10;
string s;
int ans;
void solve() {
    bool flag = false;
    ans = 0;
    cin >> s;
    for(int i = 0; i < s.size(); i ++)
    {
        if(s[i] == '1') flag = true;
        if(s[i] == '0' && flag)
        {
            int j = i + 1;
            while(s[j] != '1' && j < s.size())   j ++;

            if(s[j] == '1' && j < s.size()) ans++;
        }
    }
    cout << ans << endl;
    return ;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return Accept;
}