【LGR-062】洛谷10月月赛 III div.2 （A-C）

前言

100+100+46+0=246pts 300多名

以后每次比赛都要有进步哦！qwq

小D与笔试

水题

Code

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
int n,q;
map<string,string> s;
int main()
{
    n = read(), q = read();
    for(int i=1;i<=n;++i) {
        string a,b;
        cin>>a>>b; s[a] = b;
    }
    for(int i=1;i<=q;++i) {
        string a,b,c,d,e;
        cin>>e>>a>>b>>c>>d;
        if(s[e] == a) cout<<"A"<<endl;
        if(s[e] == b) cout<<"B"<<endl;
        if(s[e] == c) cout<<"C"<<endl;
        if(s[e] == d) cout<<"D"<<endl;
    }
    return 0;
}
/*
3 4
decoak yes
duliuchutiren nonono
csps noiptg
decoak yes no qwq qaq
csps noiptg noippj noi cspj
decoak qwq qaq yesyes yes
duliuchutiren yes no nono nonono

A
A
D
D
*/

小E与美食

水题。但是卡精度

Code

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#define int long long
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
const int N = 3e5+7;
int n;
int a[N];
bool cmp(int x,int y) {
    return x > y;
}
signed main()
{
    int n = read();
    for(int i=1;i<=n;++i)
        a[i] = read();
    sort(a+1, a+1+n, cmp);
    double maxx = 0.0; double sum = 0.0;
    for(int i=1;i<=n;++i) {
        sum += a[i];
        double ss = sum*sum;
        double tmp = (double)(ss*1.0/i*1.0);
        maxx = max(maxx,tmp);
    }
    printf("%.8lf\n",maxx);
    return 0;
}
/*
2
2 1

4.50
*/

小C与桌游

拓扑排序 + 贪心

但是贪心要考虑全面，在求ans2（就是第二问的时候），要将能去的点（now<last）全部走一遍，这样再找出来的最大值才是最优走法

实力不足，码力有限。冷静分析，考虑全面。

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
const int N = 5e5+7;
int n,m,ans1,ans2;
int du1[N],du2[N];
bool vis[N];
vector<int> E[N];
struct Node {
    int x,y;    //×??o￡??ù×ó 
};
priority_queue<int,vector<int>,greater<int> > q1;   //??¨￠? |ìY?? ?á???¨? 
queue<int> q3;
priority_queue<int> A;
void topo() {
    for(int i=1;i<=n;++i)
        if(!du1[i]) q1.push(i), A.push(i);
    int last = 0;
    while(!q1.empty()) {    //?¨°|ì??á??¨¤?á? 
        int u = q1.top(); q1.pop();
        if(u > last) ans1++, last = u;
        for(int i=0;i<E[u].size();++i) {
            int v = E[u][i]; du1[v]--;
            if(!du1[v]) q1.push(v);
        }
    }
    last = 0;
    while(!A.empty()) {
        while(!A.empty()) {
            int now = A.top(); A.pop();
            if(now > last) {
                last = now; ++ans2;
            }
            q3.push(now);
        }
        while(!q3.empty()) {
            int now = q3.front(); q3.pop();
//          printf("now = %d\n",now);
            for(int i=0;i<E[now].size();++i) {
                int to = E[now][i]; --du2[to];
                if(!du2[to]) {
                    if(to < last) q3.push(to);
                    else A.push(to);
                }
            }
        }
//      printf("Atop = %d\n",A.top());
    }
}
int main()
{
    n = read(), m = read();
    for(int i=1,u,v;i<=m;++i) {
        u = read(), v = read();
        E[u].push_back(v); du1[v]++; du2[v]++;
    }
    topo();
    ans1 = min(ans1,1919810);
    ans2 = min(ans2,1919810);
    printf("%d\n%d\n",ans1,ans2);
    return 0;
}
/*
3 2
1 2
1 3

3
2
*/