首页 > 其他分享 >8.7 个人赛

8.7 个人赛

时间：2023-08-09 17:58:19浏览次数：33  
标签：cout 8.7 int res cin long 个人赛 define

比赛链接: https://www.luogu.com.cn/contest/123979#description


A - Phone List

难度 ⭐

解题思路

一道比较裸的trie树的题; 但是我在题解中发现了一个很有意思的做法, 就是通过把字符串进行排序, 如果存在a是b的前缀, 那个a和b一定紧挨着;

神秘代码

//正常做法
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
int n, idx;
int tr[N][10], h[N];
void ins(string s) {
    int p = 0;
    for (int i = 0; i < s.size(); i++) {
        int u = s[i] - '0';
        if (tr[p][u] == 0) tr[p][u] = ++idx;
        p = tr[p][u];
    }
    h[p]++;
}
bool find(string s) {
    int p = 0;
    for (int i = 0; i < s.size()-1; i++) {
        int u = s[i] - '0';
        p = tr[p][u];
        if (h[p]) return true;
    }
    return false;
}
void solve() {
    memset(tr, 0, sizeof tr);
    memset(h, 0, sizeof h);
    idx = 0;
    cin >> n;
    vector<string> v;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        v.push_back(s);
        ins(s);
    }
    for (auto t : v) {
        if (find(t)) {
            cout << "NO" << endl;
            return;
        }
    }
    cout << "YES" << endl;
    return;
}
signed main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

//技巧做法
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
int n, idx;
void solve() {
    cin >> n;
    vector<string> v;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
       v.push_back(s);
    }
    sort(v.begin(),v.end());
    for(int i=1;i<v.size();i++){
        string a=v[i-1],b=v[i];
        int len=a.size();
        if(b.substr(0,len)==a){
            cout<<"NO"<<endl;
            return;
        }
    }
    cout<<"YES"<<endl;
    return ;
}
signed main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}



B - Physics Problem

难度 ⭐⭐

解题思路

这个题如果能看懂题目给的提示就很好做了, 题目里说任意两个状态之间一定存在间接或直接的转换关系, 意思就是该图是一个存在环的连通图; 题目的输入相当于给了图中所有的直接关系, 一共有m个, 因为是连通图, 所以除了这m个外其他的都是间接关系, 而点和点之间的关系一个有C(n,2)个, 也就是在n个点中任取2个, 然后减去m就是正确答案;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
const int N = 1e6 + 10;
int n, m;
signed main() {
    IOS;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
    }
    cout << n * (n - 1) / 2 - m;
    return 0;
}



C - 英语1（eng1）- 英语作文

难度 ⭐

解题思路

用map把所有单词的含金量存起来; 把作文以空格分隔开可以用stringstream, 具体操作见代码; 记得剔除分隔符和不区分大小写;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
const int N = 1e6 + 10;
int n, m, p, res;
map<string, int> mp;
signed main() {
    IOS;
    cin >> n >> p;
    for (int i = 1; i <= n; i++) {
        string s;
        int a;
        cin >> s >> a;
        mp[s] = a;
    }
    string s = "";
    string t;
    while (getline(cin, t)) s += t;
    stringstream ss(s);
    while (ss >> t) {
        bool f = false;
        string str = "";
        for (int i = 0; i < t.size(); i++) {
            if (t[i] == '.' || t[i] == ',' || t[i] == '?' || t[i] == '!') {
                res = (res + mp[str]) % p;
                str = "";
            }
            else str += t[i];
        }
        res = (res + mp[str]) % p;
    }
    cout << res;
    return 0;
}



D - 游园安排

难度 ⭐⭐

解题思路

本质还是找最长上升子序列的线性dp, 注意本题不区分大小写;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
const int N = 1e6 + 10;
int n, m, p, maxn;
string dp[N];
string res[N];
vector<string> v;
signed main() {
    IOS;
    string s;
    string t;
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] >= 'A' && s[i] <= 'Z') {
            v.push_back(t);
            t = s[i];
        }
        else t += s[i];
    }
    v.push_back(t);
    int len = 0;
    for (int i = 0; i < v.size(); i++) {
        int l = 0, r = len;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (dp[mid] < v[i]) {
                l = mid;
            }
            else r = mid - 1;
        }
        dp[r + 1] = v[i];
        res[r + 1] = res[r] + v[i];
        len = max(len, r + 1);
    }
    cout << res[len];
    return 0;
}



E - 数正方形

难度 ⭐⭐

解题思路

又是一道思维题, 先算正着的子正方形, 很容易得知是(n - i) * (n - i), i是子正方形的边长; 本题主要是计算斜着是子正方形, 为了防止重复计算, 我们要保证该子正方形是大正方形才有的, 也就是说该子正方形的四个顶点都要在大正方形的四条边上, 在纸上多画几个会找到规律: 边长为n的正方形的边上除了两个顶点外有n-1个点, 这n-1个点都可以作为子正方形的一个顶点; 所以对于一个边长为n的正方形, 他包含了(1+(n-1))个子正方形, 也就是n个;
注意本题的n是点数, 边长是n-1;

神秘代码

    #include<bits/stdc++.h>
    #define int long long
    #define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    using namespace std;
    const int N = 1e6 + 10, mod = 1e9 + 7;
    int n, res;
    signed main() {
        cin >> n;
        for (int i = 1; i < n; i++) {
            res = (res + i * (n - i) * (n - i)%mod) % mod;
        }
        cout << res;
        return 0;
    }



F - 自适应 PVZ

难度 ⭐⭐⭐

解题思路

一道区间贪心的题目; 因为我们要把尽可能多的不冲突的区间相连, 所以可以把所有僵尸的出现时间段按右节点从小到大排序, 这样可以让序列尽可能的紧凑; 有m个豌豆射手我们就可以设置m个平行的序列, 并且受到线性dp的启发, 我们可以把序列的最后一个右节点用来代表整个序列; 在连接时, 对于一个时间段(左节点为l, 右节点为r), 我们可以在现有的所有序列中找到小于l的最大右节点R, 然后把这个时间段接到该序列后面, 这样就保证了序列的紧凑性; 因为要插入后排序, 所以我们可以用set来存所有序列的末尾节点; 如果所有序列的末尾节点都大于该时间段的右节点, 这时候如果还能看序列就新开一个序列, 否则就只能让过去;
这里还有一个小插曲, set的lower_bound函数只能用来找第一个大于等于给定值的数, 而我们的需要是找最后一个小于等于给定值的数, 找了很多资料发现不能通过修改比较器或者调整顺序来做到; 所以我只好用upper_bound函数找到第一个大于给定值的数, 然后用prev函数取它的前一个数的迭代器, 这个迭代器指的数就是最后一个小于等于给定值的数, 如果upper_bound返回的迭代器是begin()所有序列的末尾节点都大于该时间段的右节点; 搜了好长时间最后还是找的newbing才给我说明白...人工智能改变生活啊...

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6+10, mod = 1e9 + 7;
int n, m;
PII f[N];
multiset<int> s;
bool cmp(PII a, PII b) {
    return a.second < b.second;
}
signed main() {
    IOS;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
        f[i] = { a,b };
    }
    sort(f + 1, f + 1 + n, cmp);
    int num = 1, res = 0;
    s.insert(f[1].second);
    for (int i = 2; i <= n; i++) {
        int a = f[i].first, b = f[i].second;
        auto t = s.upper_bound(a);
        if(t==s.begin()){
            if (num < m) {
                num++;
                s.insert(b);
            }
            else res++;
        }
        else {
            t = prev(t);
            s.erase(t);
            s.insert(b);
        }
    }
    cout << res;
    return 0;
}



I - 柯基棋

难度 ⭐

解题思路

博弈论, A先下; 如果n为奇数, A可以先下正中间, 并且之后的每一步都根据B下的位置在其中心对称的位置下, 这样下去A必胜; 如果n为偶数就反过来了, A成了被模仿的一方, 这样就是B必胜;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e4 + 10;
int n, m;
signed main(){
	int t;
	cin>>t;
	while(t--){
		int n,a,b;
		cin>>n>>a>>b;
		if(n%2==1) cout<<"A won"<<endl;
		else cout<<"B won"<<endl;
	}
}

标签：cout,8.7,int,res,cin,long,个人赛,define
From： https://www.cnblogs.com/mostimali/p/17617537.html

相关文章

  • 8.7总结
    今天相对来说就轻松多了，没有学姐找我，也就定时发一篇推文，原来还在想为啥学长想退部，现在原因明了。今天也没干啥事，在摆乱，不愿意动，发现背上全是那种小疙瘩，去拿药了，说是代谢紊乱，应该是这几天比较焦虑吧......
  • 云原生周刊：KubeCon China 2023 详细议程公布 | 2023.8.7
    开源项目推荐SpiderpoolSpiderpool是一个Kubernetes底层网络解决方案。它提供丰富的IPAM功能和CNI集成能力，为开源社区的CNI项目提供支持，允许多个CNI有效协作。它能让底层CNI在裸机、虚拟机和任何公共云等环境中完美运行。PreevyPreevy是一款功能强大的命令行界......
  • 闲话8.7
    昨晚管神讲太晚了所以咕到8.8来写了上午博弈论和杂题，依旧听不懂......
  • 2023.8.7
    今天依旧早起去了小河沿早市，吃了很多好吃的而且物价很便宜接着骑自行车去了中街，真的很喜欢在城市里瞎溜达的感觉！！！中街很大，旁边还有其他商城，我很满意。这次旅行出乎意料地重新联系上一个朋友，已经几年没和他说话，但是狗哥说话还是这么贱地气死人（暴怒）昨天晚上和朱朱各种给人打电话......
  • 2023.8.7
    今天把花式栈溢出的framefaking结束了，并且记成了笔记，查东西的时候发现活用最近兴起的ai生成挺有用的，可以很方便地查到很多基础知识，比如pwntools的一些函数，到pwntools官网去查，就感觉查起来有点难受，而且还不一定能找到满意的解答，用ai生成的答案，虽然也不能保证一定正确，但至少也有不......
  • 2023.8.7 练习
    ARC060D若\(b^2\len\)，此时\(b\)很小，直接枚举即可。若\(\sqrt{n}<b<n\)，此时发现其只有两位。那么\(n\bmodb+n/b=s\)，即\((n/b)*(b-1)=n-s\)，考虑枚举\(n-s\)的约数判断即可。ARC060E考虑借用“弹飞绵阳”一题的套路，先分块，然后预处理出\(cnt_i,nxt_i\)，表示走出这个块......
  • 2023.8.7
    Bronya19C场。转圈圈一个长为\(n\)的\(01\)串\(S\)，串中有且仅有一个\(1\)，你可以操作若干次，每次可以将一个长为\(k\)的子串反转。对每个\(i\)询问\(1\)至少几步可以翻转到位置\(i\)，另外地，一些位置在操作的过程中不能有\(1\).对于\(i\)，如果不存在这个最小步数，输......
  • 2023.8.7 模拟赛
    A有一个01串，只有一位是\(1\)，你每次可以翻转一个长为\(k\)的串，求出使得每个位置为\(1\)最少翻转多少次。其中有一些位是存在\(1\)的。\(n10^5\)考虑求出一个点能翻转一次到哪些点，只要不碰到边界即可。考虑线段树优化建图，建立奇偶两颗线段树。然后deque优化BFS......
  • 8.7
    #include<bits/stdc++.h>usingnamespacestd;vector<int>vec[100000];//存关系图boolvis[100000];//标记五服以内的亲属charsex[100000];//记录性别boolflag;//标记情侣是否为近亲voidDfs(intx,intnum)//num表示第几代，从0开始{if(num>=4)return;......
  • 暑假周记（8.7）
    昨天晕车吐得导致今天都难受，直接跟老妈请假不上课了，歇了一天。staticStringcopyValueOf(char[]data)：返回指定数组中表示该字符序列的StringstaticStringcopyValueOf(char[]data,intoffset,intcount)：返回指定数组中表示该字符序列的StringbooleanendsWith(Stringsuffi......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99