Educational Codeforces Round 104 (Rated for Div. 2)（VP）(寒假ACM模拟赛2)

VP时间

A.找到最小，计算最小有几个

n-cnt;

1.ac

B.结论

模拟会超时

n&1:

n/2;相遇A继续走，B跳两格到n/2+1(n/2-1->n/2+1)

k<n/2就直接输出

n>k>n/2输出k+1

模拟一下 1234,12345

!n&1不会改变位置，直接输出k%n

n&1 找什么时刻会发现冲突

每一个周期冲突2次，

C.

偶数队伍就需要0

奇数队伍就1，-1，1，-1交替

D.

消C

a=sqrt(2*b+1);

c=b+1;

找范围暴力算

b<=n

a<=sqrt(2*n+1);

c<=n-1

n=1e9

min(n,1e5+9);

枚举a

!(pow(a,2)-1%2)ans++;

题解

A.
?

// Problem: A. Arena
// Contest: Codeforces - Educational Codeforces Round 104 (Rated for Div. 2)
// URL: https://codeforces.com/group/RAx5fiilkP/contest/1487/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//へ　　　　　／|
//　　/＼7　　　 ∠＿/
//　 /　│　　 ／　／
//　│　Z ＿,＜　／　　 /`ヽ
//　│　　　　　ヽ　　 /　　〉
//　 Y　　　　　`　 /　　/
//　ｲ●　､　●　　??〈　　/
//　()　 へ　　　　|　＼〈
//　　>ｰ ､_　 ィ　 │ ／／
//　 / へ　　 /　ﾉ＜| ＼＼
//　 ヽ_ﾉ　　(_／　 │／／
//	　　7　　　　　　　|／
//	　　＞―r￣￣`ｰ―＿
#include <iostream>
#include <cstring>
#include <iomanip>
#include <ctime>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define eps 1e-5
#define INF 1e9
using namespace std;
typedef long long ll;
const int N = 2e6 + 9;
int a[N];
void solve() {
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int mn=INF;
	for(int i=1;i<=n;i++){
		mn=min(mn,a[i]);
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(mn==a[i]){
			cnt++;
		}
	}
	cout<<n-cnt<<'\n';
	
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int q;
	cin >> q;
	while (q--) {
		solve();
	}

	return 0;
}

B.

根据行动路线可以画一个环

偶数环 (n=4)可以发现它们不会相遇，在k时刻时cout<<(k%n?k%n:0)<<'\n'; or (k-1)mod n+1

k==n时 nmodn=0;不正确?(故k-1)

奇数环 (n=5)可以发现相遇周期（t=(n-1/2))就是走k步后又多走（k/(t)）步,防止(k==0)

因此cout<<(k-1+(k-1/（t)))%n+1<<'\n';

// Problem: B. Cat Cycle
// Contest: Codeforces - Educational Codeforces Round 104 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1487/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//へ　　　　　／|
//　　/＼7　　　 ∠＿/
//　 /　│　　 ／　／
//　│　Z ＿,＜　／　　 /`ヽ
//　│　　　　　ヽ　　 /　　〉
//　 Y　　　　　`　 /　　/
//　ｲ●　､　●　　??〈　　/
//　()　 へ　　　　|　＼〈
//　　>ｰ ､_　 ィ　 │ ／／
//　 / へ　　 /　ﾉ＜| ＼＼
//　 ヽ_ﾉ　　(_／　 │／／
//	　　7　　　　　　　|／
//	　　＞―r￣￣`ｰ―＿
#include <iostream>
#include <cstring>
#include <iomanip>
#include <ctime>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define eps 1e-5
#define INF 1e9
using namespace std;
typedef long long ll;
void solve() {
	int n,k;
	cin>>n>>k;
	k--;//防止k==n cout<<0,之后补+1即可
	if(n&1){
		int t=(n-1)/2;
		cout<<(k+(k/t))%n+1<<'\n';
	}else{
		cout<<k%n+1<<'\n';
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int q;
	cin >> q;
	while (q--) {
		solve();
	}

	return 0;
}

C.

一共n个队

积分应该是kn分

每个队平均下来k分

胜负场x场

平局场y场

所以存在下面两个式子

得到

要求平局数最小

故k最大

当n为奇数时,?,,,每个队赢把

当n为偶数时,,,,每个队赢把

// Problem: C. Minimum Ties
// Contest: Codeforces - Educational Codeforces Round 104 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1487/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//へ　　　　　／|
//　　/＼7　　　 ∠＿/
//　 /　│　　 ／　／
//　│　Z ＿,＜　／　　 /`ヽ
//　│　　　　　ヽ　　 /　　〉
//　 Y　　　　　`　 /　　/
//　ｲ●　､　●　　??〈　　/
//　()　 へ　　　　|　＼〈
//　　>ｰ ､_　 ィ　 │ ／／
//　 / へ　　 /　ﾉ＜| ＼＼
//　 ヽ_ﾉ　　(_／　 │／／
//	　　7　　　　　　　|／
//	　　＞―r￣￣`ｰ―＿
#include <iostream>
#include <cstring>
#include <iomanip>
#include <ctime>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define eps 1e-5
#define INF 1e9
using namespace std;
typedef long long ll;
const int N = 2e6 + 9;
int a[N];
void solve() {
	int n;
	cin>>n;
	int cnt=n*(n-1)/2;
	if((n&1)){
		for(int i=1;i<=cnt;i++){
			if(i&1){
				cout<<1<<" ";
			}else{
				cout<<-1<<" ";
			}
		}
	}else{
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				if(j-i<n/2){
					cout<<1<<" ";
				}else if(j-i==n/2){
					cout<<0<<" ";
				}else{
					cout<<-1<<" ";
				}
			}
		}
		
	}
	cout<<'\n';
	


}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int q;
	cin >> q;
	while (q--) {
		solve();
	}

	return 0;
}

D.

// Problem: D. Pythagorean Triples
// Contest: Codeforces - Educational Codeforces Round 104 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1487/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//へ　　　　　／|
//　　/＼7　　　 ∠＿/
//　 /　│　　 ／　／
//　│　Z ＿,＜　／　　 /`ヽ
//　│　　　　　ヽ　　 /　　〉
//　 Y　　　　　`　 /　　/
//　ｲ●　､　●　　??〈　　/
//　()　 へ　　　　|　＼〈
//　　>ｰ ､_　 ィ　 │ ／／
//　 / へ　　 /　ﾉ＜| ＼＼
//　 ヽ_ﾉ　　(_／　 │／／
//	　　7　　　　　　　|／
//	　　＞―r￣￣`ｰ―＿
#include <iostream>
#include <cstring>
#include <iomanip>
#include <ctime>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define eps 1e-5
#define INF 1e9
using namespace std;
typedef long long ll;
const int N = 2e6 + 9;
int a[N];
int n;
bool check(int a,int b,int c){
	return c*c==a*a+b*b;
}
void solve() {
	cin>>n;
	ll ans=0;
	n=sqrt(2*n-1);
	for(int i=2;i<=min(n,100009);i++){
		if(((i*i)-1)%2==0){
			ans++;
		}
	}
	cout<<ans<<'\n';


}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int q;
	cin >> q;
	while (q--) {
		solve();
	}

	return 0;
}