别问,问就是我真的很菜

2021ccpc女生赛模拟3,题目来源2018ccpc省赛,题目在hdu里面都有(女?)

这次真的给我整不会了,又是一次愉快的面向题解编程了….

A - Easy $h$-index

简单,但是这只是一个开始,后面BC都是这个引用论文的主题

稍微推一下就行了

#include<iostream>
using namespace std;

const int maxn=2e5+7;
int paper[maxn];

int main(){
    int n;
    while(cin>>n){
        for(int i=0;i<=n;i++){
            cin>>paper[i];
        }
        int sum=0;
        for(int i=n;i>=0;i--){
            sum+=paper[i];
            if(sum>=i) {
                cout<<i<<endl;
                break;
            }
        }
    }
}

B - Higher $h$-index

我不懂,但我大受震撼

#include<iostream>
using namespace std;
typedef long long ll;
int main(){
    ll n,a;
    while(cin>>n>>a){
        cout<<(n+a)/2<<endl;
    }
}

顺带这个是我的原版代码,一直WA是为什么呢?

#include<iostream>
using namespace std;
typedef long long ll;
int main(){
    ll n,a;
    while(cin>>n>>a){
        if(a==n) cout<<n<<endl;
        else{
            ll sum=0;
            for(ll i=n-1;i>=0;i--){
                sum=sum+1+a;
                if(sum>=i) {
                    cout<<i<<endl;
                    break;
                }
            }
        }
    }
}

C - Just $h$-index

线段树,下次一定T_T

D - Circular Coloring

E - From Tree to Graph

F - Sorting

被坑到了,然后还去问了下double的取值范围,据大佬说跟long long差不多?

这个题WA是因为除法,卡小数后面精度

然后,把给的那个式子左右乘开,化简

这里还学到了一点小知识,如果comp函数里面写<=号的话,可能会出一些意想不到的问题,比如样例3,三行算出来都一样就要按原顺序输出,如果用<=,输出结果不是123 而是321

所以应该在数值相等的时候进行序号的比较

emmmm突然想起来上学期期中考试考过这种类似的还比这个简单好多为什么当时就没想到用结构体然后排序呢…

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e4+7;
struct tuples{
    ll a,b,c;
    int p;
}t[maxn];
bool comp(tuples a,tuples b){
    if((a.a*b.c+a.b*b.c)!=(b.a*a.c+b.b*a.c))
        return (a.a*b.c+a.b*b.c)<(b.a*a.c+b.b*a.c);
    else return a.p<b.p;
}
int main(){
    int n;
    while(cin>>n){
        for(int i=1;i<=n;i++){
            cin>>t[i].a>>t[i].b>>t[i].c;
            t[i].p=i;
        }
        sort(t+1,t+n+1,comp);
        for(int i=1;i<n;i++){
            cout<<t[i].p<<' ';
        }
        cout<<t[n].p<<endl;
    }
}

G - String Transformation

字符串,,那没事了

H - Infinity

I - Longest Increasing Subsequence

J - Vertex Cover

K - 2018

直接进行一个题解的看和一个注释的写

https://blog.csdn.net/weixin_38378637/article/details/81368033?utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-1.no_search_link&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-1.no_search_link

(大佬写的太好了)

#include<iostream>
using namespace std;
typedef long long ll;
ll fac(ll l,ll r,ll x){//*计算l,r内的x的倍数个数
    return r/x-(l-1)/x;
}
int main(){
    ll a,b,c,d;
    while(cin>>a>>b>>c>>d){
        ll ans=0;
        //容斥原理
        ans+=fac(a,b,2018)*(d-c+1);//区间a,b选择2018的倍数,cd中任意数
        ans+=fac(c,d,2018)*(b-a+1);//区间c,d选择2018的倍数,ab任意
        ans-=fac(a,b,2018)*fac(c,d,2018);//容斥原理,去掉上面两行中重复计算的部分
        ans+=(fac(a,b,1009)-fac(a,b,2018))*(fac(c,d,2)-fac(c,d,2018));
        //1009的奇数倍(偶数倍与2018的重复),与另一集合中的偶数(去掉2018的重复)相乘,仍旧得到2018的倍数
        //-------------------------------------↑这里重复的情况 比如说1009*2==2018*1
        ans+=(fac(c,d,1009)-fac(c,d,2018))*(fac(a,b,2)-fac(a,b,2018));
        cout<<ans<<endl;
    }
}