Noip2016 四校联考 FJSDFZ Round 2

tonyfang posted @ 2016年11月06日 22:17 in 随笔 with tags c++ OI , 710 阅读

1. rope

         有$n$个球排成一列挂在空中,第i个球与第i+1个球用绳子或者弹簧相连,第$n$个球与天花板相连,现在剪断第i个球与第$i+1$个球之间的绳子或弹簧(或是第$n$个球与天花板之间的绳子或弹簧),你的任务是计算剪断后每个球的加速度/当地重力加速度的值。

$n \leq 100$

【题解】受力分析发现只影响cut的上面的第一个弹簧到下面的第一个弹簧这之间的部分。

然后讨论下就行了。

 

# include <stdio.h>
// # include <bits/stdc++.h>

using namespace std;

int n, t[110], cut;
double w[110];
double a[110];

int main() {
	freopen("rope.in", "r", stdin);
	freopen("rope.out", "w", stdout);
	scanf("%d", &n);
	for (int i=1; i<=n; ++i)
		scanf("%lf%d", &w[i], &t[i]);
	scanf("%d", &cut);
	int upf = 0;    // actually down
	double upall = 0.0, ups = 0.0;
	for (int i=cut-1; i>=1; --i) {
		if(t[i] == 1) {
			upf = i;
			break;
		}
		ups += w[i];
	}
	upall = ups;
	for (int i=upf; i>=1; --i)
		upall += w[i];
	
	int downf = n;    // actually up
	double downs = 0.0;
	for (int i=cut+1; i<=n; ++i) {
		downs += w[i];
		if(t[i] == 1) {
			downf = i;
			break;
		}
	}
	
//	printf("%d %d %.3lf %.3lf %.3lf\n", upf, downf, ups, downs, upall);
	
	for (int i=upf; i>=1; --i) a[i] = 0;
	for (int i=downf+1; i<=n; ++i) a[i] = 0;
	for (int i=upf+1; i<=cut; ++i) 
		a[i] = (double)(upall+w[cut])/(ups+w[cut]);
	
	if(downf != n) {
		for (int i=cut+1; i<=downf; ++i)
			a[i] = (double)(upall+w[cut])/downs, a[i] = -a[i];
	} else {
		for (int i=cut+1; i<=n; ++i)
			a[i] = 0;
	}
	
	for (int i=1; i<=n; ++i) printf("%.2lf\n", a[i]);
	return 0;
}

2. triangle

在一个圆周上分布着n个节点,每2个节点之间用红色线或蓝色线连接,你的任务是统计三条边同色的三角形数目。

$n \leq 1000, T \leq 5$。

【题解】

统计异色三角形数目,然后用总数$\frac{n(n-1)(n-2)}{6}$减去即可。

考虑如何统计异色三角形:一定有一对异色边连在同一个点上,统计这种边的对数后除以2即可。

 

# include <stdio.h>
// # include <bits/stdc++.h>

using namespace std;

const int M = 1010;
int T, n, a[M][M];
typedef long long ll;
ll ans = 0;

int main() {
	freopen("triangle.in", "r", stdin);
	freopen("triangle.out", "w", stdout);
	scanf("%d", &T);
	while(T--) {
		ans = 0;
		scanf("%d", &n);
		for (int i=1; i<=n; ++i) {
			a[i][i] = 0;
			for (int j=i+1; j<=n; ++j)
				scanf("%d", &a[i][j]);
		}
		
		for (int i=1; i<=n; ++i)
			for (int j=1; j<i; ++j)
				a[i][j] = a[j][i];
				
		for (int i=1; i<=n; ++i) {
			int A=0, B=0;
			for (int j=1; j<=n; ++j) {
				if(i == j) continue;
				A += (a[i][j] == 1);
				B += (a[i][j] == 0);
			}
			ans += (ll)A*B;
		}
		ll all = (ll)n * (n-1) * (n-2) / 6;
		ans = all - ans/2;
		printf("%lld\n", ans);
	}
	return 0;
}

3. code

给出一段代码,求对于给定的数据,输出“Find”的概率对于$10^9+7$取模。

 

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<set>
using namespace std;
set<int>st;
int main()
{
	srand(time(NULL));
	int n,m;
	cin>>n>>m;
	while (n>0)
	{
		n=rand()%n;
		st.insert(n);
	}
	for (int i=1;i<=m;i++)
	{
		int check;
		cin>>check;
		if (st.count(check)==0)
		{
			cout<<"Not find"<<endl;
			return 0;
		}
	}
	cout<<"Find"<<endl;
	return 0;
}

$m \leq n \leq 1000, -1000 \leq check \leq 1000$

【题解】

可以证明,答案就是把所有不同的$(check+1)$乘起来取个逆元即可。

 

# include <stdio.h>
# include <algorithm>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int M = 500010, mod = 1e9+7;
int n, m, a[110];
bool cnt[110];

inline int pwr(int x, int y) {
	int ret = 1;
	while(y) {
		if(y&1) ret = 1ll * ret * x % mod;
		x = 1ll * x * x % mod;
		y >>= 1;
	}
	return ret;
}

int main() {
	freopen("code.in", "r", stdin);
	freopen("code.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for (int i=1; i<=m; ++i) {
		scanf("%d", &a[i]);
		if(a[i]<0 || a[i]>=n) {
			puts("0");
			return 0;
		} 
		cnt[a[i]]=1;
	}
	int ans = 1;
	for (int i=0; i<n; ++i) 
		if(cnt[i]) ans = 1ll * ans * (i+1) % mod;
	printf("%d\n", pwr(ans, mod-2));
	return 0;
}
networkslog.com 说:
2023年4月18日 17:26

Canara Bank has thousands of branch and ATM locations throughout the country.We discuss, review, write about, and explain various products, services, technology, and other topics on our website, which is solely for learning and networkslog.com educational reasons. Having said that, we make every effort to keep the material up to date. There are various methods for checking Canara Bank balance. Find each method and Canara Bank balance check number for each type to obtain on demand... Canara Bank is one of India's largest banks, with over a million active customers.

roblox en ligne conn 说:
2023年7月18日 18:15

Roblox est un important fournisseur de services de jeux en ligne qui a connu un succès croissant ces dernières années. Vous pouvez utiliser Roblox Studio pour créer vos propres jeux ou jouer à des jeux créés par d’autres joueurs. roblox en ligne connexion L’application Roblox est disponible en téléchargement gratuit sur Android, iOS, Windows et d’autres plateformes. Mais si vous ne souhaitez pas télécharger l’application, il existe un autre moyen d’y accéder. Roblox est en ligne gratuitement sans avoir à télécharger l’application.

Odisha 4th Class Sy 说:
2023年7月19日 21:05

Odisha Board 4th Syllabus work to Promote the Advancement of Education in General, With the help of Syllabus, Students can easily make out what Topics to Focus on more, as it Provides the marks Distribution of each unit. They can Prepare their Study plan by Focusing on the Topics that carry more weight age.Here, we bring you the SCERT Odisha 4th new Syllabus 2024, We have Collected and Odisha 4th Class Syllabus 2024 Aggregated the Syllabus, so that Students can easily Access and Study them. The Language used in the Odisha Board Primary Syllabus 2024 are Simple and lucid. It tries to enhance the Visual Appeal and also to explain more complex concepts with the help of illustrations in the Syllabus.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter