codeforces gym 102058——————HPU ICPC国庆训练1

Bertha 。 2023-06-06 03:42 5阅读 0赞

题目来源：[https://codeforces.com/gym/102058][https_codeforces.com_gym_102058]

### 目录 ###

*  E. Fractions
 *  K. Voronoi Diagram Returns
 *  L. Repetitive Palindrome
 *  M. Coke Challenge

# E. Fractions #

官方题解：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hwdWVyX1JhbmRvbQ_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hwdWVyX1JhbmRvbQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hwdWVyX1JhbmRvbQ_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hwdWVyX1JhbmRvbQ_size_16_color_FFFFFF_t_70 3]

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll A,B,C,D;
    int gcd(int a,int b) {
        
            return !b?a:gcd(b,a%b);
    }
    
    ll F(ll P, ll Q) {
        
            ll ans = 0;
            for(int p=1;p<1000;++p)
                    for(int q=1;q<1000;++q)
                            if(gcd(p,q)==1 && p+q<1000) {
        
                                    ans += min(P/p, Q/q);
                            }
            return ans;
    }
    
    int main() {
        
            cin>>A>>B>>C>>D;
            cout<<F(B,D) - F(A-1,D) - F(B,C-1) + F(A-1,C-1)<<endl;        
            return 0;
    }

比赛时写的

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll A,B,C,D;
    int gcd(int a,int b) {
        
            return !b?a:gcd(b,a%b);
    }
    int main() {
        
            while(cin>>A>>B>>C>>D) {
        
                    ll ans = 0;
                    int n = 1000;
                    for(int i=1;i<n;++i)
                            for(int j=1;j<n;++j)
                                    if(gcd(i,j)==1 && i+j<=999) {
        
                                            ll a = ceil((double)A*(double)j/(double)i), b = B*j/i;
                                            if(a>D || b<C) continue;
                                            if(a<C) a = C;
                                            if(D<b) b = D;
                                            ans += min(B/i - (A-1)/i, b/j-(a-1)/j);
                                    }
                    cout<<ans<<endl;
            }
            return 0;
    }

# K. Voronoi Diagram Returns #

读懂题就能做

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 2e3+7;
    double x[MAXN],y[MAXN];
    int n,q,qx,qy;
    
    double getdis(int i) {
        
            return (x[i]-qx)*(x[i]-qx) + (y[i]-qy)*(y[i]-qy);
    }
    
    int main() {
        
            ios::sync_with_stdio(0);
            cin>>n>>q;
            for(int i=0;i<n;++i)    cin>>x[i]>>y[i];
            while(q--) {
        
                    cin>>qx>>qy;
                    double mindis = 1000000000.0;
                    double dis;
                    int id1,id2,cnt = 0;
                    for(int i=0;i<n;++i) {
        
                            dis = getdis(i);
                            if(dis<mindis) {
        
                                    mindis = dis;
                                    id1 = i+1;
                                    cnt = 1;
                            }
                            else if(dis == mindis) {
        
                                    id2 = i+1;
                                    cnt++;
                            }
                    }
                    if(cnt==1)      cout<<"REGION "<<id1<<endl;
                    if(cnt==2)      cout<<"LINE "<<id1<<" "<<id2<<endl;
                    if(cnt>2)       cout<<"POINT"<<endl;
    
            }
            return 0;
    }

# L. Repetitive Palindrome #

给定一个由小写字母组成的字符串  s s s 和整数  k k k 。

t t t 是由  k k k 个  s s s 顺序连接构成的新字符串。判断t是否是一个回文。

即  t = s s s ⋯ s s ⏟ k      c o p i e s \\large t=\\underbrace\{sss\\cdots ss\}\_\{k\\;\\; copies\} t=kcopiessss⋯ss

Check whether s is palindrome in O(|s|) time

是否是一个回文字符串

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    
    int main() {
        
            string s;
            ll k;
            cin>>s>>k;
            string t = s;
            reverse(t.begin(),t.end());
            if(s==t)        cout<<"YES"<<endl;
            else            cout<<"NO"<<endl;
            return 0;
    }

# M. Coke Challenge #

郑先生真的很喜欢可乐。他很爱喝可乐，每天都不例外。一天，他决定在大田举办一场可乐比赛。获胜者将得到一盒可乐!

N N N 个人参加了比赛。每位参赛者均可获赠可乐  K K K 毫升，最先喝完可乐者即为优胜者。但是一次性喝完一整瓶可乐是很痛苦的，所以每个人都会重复喝可乐，然后休息一下。更具体地说，一旦比赛开始，第i个参与者开始喝  t i t\_i ti 秒，然后休息  s i s\_i si 秒，重复这个过程，直到没有更多的可乐剩下。此外，每个人每秒喝  A A A 毫升。如果一个参赛者喝完了他/她的可乐，比赛就结束了。

根据  N N N 个参与者的信息，确定比赛结束后多少秒，因为比赛开始了。

--------------------

模拟一下

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 1e3+7;
    int s[MAXN], t[MAXN];
    int n,k,a;
    int main() {
        
            while(cin>>n>>k>>a) {
        
                    for(int i=0;i<n;++i)
                            cin>>t[i]>>s[i];
    
                    int ans = 0x3f3f3f3f;
                    for(int i=0;i<n;++i) {
        
                            int coke = 0;
                            int time = 0;
                            while(true) {
        
                                    if(coke==k){
        
                                            ans = min(ans, time);
                                            break;
                                    }
                                    if(coke+t[i]*a<k){
        
                                            time += s[i]+t[i];//休息一下
                                            coke += t[i]*a;
                                    }
                                    else {
        
                                            int num = k - coke;
                                            time += num/a;
                                            ans = min(ans, time);
                                            break;
                                    }
                            }
                    }
                    cout<<ans<<endl;
            }
            return 0;
    }

[https_codeforces.com_gym_102058]: https://codeforces.com/gym/102058
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hwdWVyX1JhbmRvbQ_size_16_color_FFFFFF_t_70]: /images/20230601/e2384d33df744e68845f973e99ec0c5b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hwdWVyX1JhbmRvbQ_size_16_color_FFFFFF_t_70 1]: /images/20230601/bd486159c9174e1aac894e7bd9ead1b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hwdWVyX1JhbmRvbQ_size_16_color_FFFFFF_t_70 2]: /images/20230601/ad3110b7f69149c091d5ffb78ab17ed6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hwdWVyX1JhbmRvbQ_size_16_color_FFFFFF_t_70 3]: /images/20230601/86e7183d15b0484b812c466118bda309.png