前言
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
*/