【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

*/

巴特西

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

前言

小D与笔试

小E与美食

小C与桌游

最新文章

热门文章