我昨天打了一下Educational Codeforces Round 104的比賽，場內做出了A,B,C,D,E五題，這場的C,D比以往簡單，
A. Arena
思路：直接找最小值出現的次數即可，
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int _;
int n;
int a[110];
void solve(){
cin >> _;
while(_--){
cin >> n;
int minn = 1e9;
for(int i = 1; i <= n; i++){
cin >> a[i];
minn = min(minn, a[i]);
}
int ans = 0;
for(int i = 1; i <= n; i++){
if(a[i] == minn){
ans++;
}
}
cout << n - ans << "\n";
}
return ;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
B. Cat Cycle
思路：剛開始被卡了一下，找規律，發現n偶數時候，不會沖突，發現n = 3，會在2，3，4，5，，，，，沖突，n = 5，會在3， 5， 7， ，，，沖突，n = 7，會在4，7，10，，沖突，根據規律推公式即可，
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int _;
ll n, k;
void solve(){
cin >> _;
while(_--){
cin >> n >> k;
if(n % 2 == 0){
cout << 1 + (k - 1) % n << "\n";
}
else{
cout << 1 + (k - 1 + ((k >= (n/2+1)) ? (1 + (k - (n/2+1))/(n/2)) : (0)))%n << "\n";
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
C. Minimum Ties
思路：構造題，n是奇數，不需要平局，一個人參加n-1場，一半勝利，一半失敗，n是偶數，一個人參加n-1場，n-1此時是奇數，所有要有一場平局，
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int _;
int n;
void solve(){
cin >> _;
while(_--){
cin >> n;
if(n % 2){
int now = n - 1;
int tim = now / 2;
for(int i = 1; i <= n-1; i++){
for(int j = 1; j <= now; j++){
if(j <= tim){
cout << "1" << " ";
}
else{
cout << "-1" << " ";
}
}
now--;
}
}
else{
int now = n - 1;
int tim = now / 2;
for(int i = 1; i <= n-1; i++){
for(int j = 1; j <= now; j++){
if(j <= tim){
cout << "1" << " ";
}
else if(j == tim + 1){
cout << "0" << " ";
}
else{
cout << "-1" << " ";
}
}
now--;
}
}
cout << "\n";
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
D. Pythagorean Triples
思路：數論題，這個數論比上一場的C簡單多了，
1
<
=
a
,
b
,
c
<
=
n
1<=a, b, c <= n
1<=a,b,c<=n范圍內找出
a
2
+
b
2
=
c
2
&
&
a
2
?
b
=
c
a^2+b^2=c^2 \&\&a^2-b=c
a2+b2=c2&&a2?b=c的情況個數，
我們先消除
a
2
a^2
a2,得：
c
2
?
b
2
=
c
+
b
c^2 - b^2 = c+b
c2?b2=c+b
c
2
?
c
=
b
2
+
b
c^2-c=b^2+b
c2?c=b2+b
c
?
(
c
?
1
)
=
b
(
b
+
1
)
c*(c-1) = b(b+1)
c?(c?1)=b(b+1)
得出：
c
=
b
+
1
c = b+1
c=b+1
可得出：
a
2
=
2
?
b
+
1
a^2=2*b+1
a2=2?b+1
我們找一下
a
,
b
,
c
a, b, c
a,b,c三個數的范圍：
1
<
=
a
<
=
n
1 <= a <= n
1<=a<=n
1
<
=
b
<
=
n
1 <= b <= n
1<=b<=n
1
<
=
c
<
=
n
1 <= c <= n
1<=c<=n
1
<
=
b
+
1
<
=
n
1 <= b+1 <= n
1<=b+1<=n
所以：
1
<
=
b
<
=
n
?
1
1 <= b <= n-1
1<=b<=n?1
此時：
3
<
=
a
2
<
=
2
?
n
?
1
3 <= a^2 <= 2*n - 1
3<=a2<=2?n?1
3
<
=
a
<
=
2
?
n
?
1
\sqrt{3} <= a <= \sqrt{2*n-1}
3
?<=a<=2?n?1
?
因為a是整數，我們要找出在
[
3
,
2
?
n
?
1
]
[\sqrt{3}, \sqrt{2*n-1}]
[3
?,2?n?1
?]中，找出
(
a
2
+
1
)
m
o
d
2
=
=
0
(a^2+1)mod2==0
(a2+1)mod2==0的數的個數，就能得到答案，我們可以通過預處理，前綴和的方式，使得每一個詢問復雜度達到
O
(
1
)
O(1)
O(1)，
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int _;
const int N = 100010;
ll sum[100010];
ll a[100010];
ll n;
void init(){
memset(a, 0, sizeof a);
memset(sum, 0, sizeof sum);
for(ll i = 2; i <= 100000; i++){
if(((i*i)-1)%2 == 0){
a[i] = 1ll;
}
}
for(int i = 1; i <= 100002; i++){
sum[i] = sum[i-1] + a[i];
}
}
void solve(){
cin >> _;
while(_--){
cin >> n;
ll k = sqrt(2ll*n-1ll);
cout << sum[k] << "\n";
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
init();
solve();
return 0;
}
E. Cheap Dinner
思路：這是一個分層圖，我們考慮dp[i][j]表示第i層選第j個的最小花費，第i層對j進行規劃的時候，要從上一層和j不沖突的dp中選一個最小值，考慮把dp結合優先佇列，
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int _;
ll dp[5][200010];
int n1, n2, n3, n4;
ll a[200010];
ll b[200010];
ll c[200010];
ll d[200010];
set<int> vec[5][200010];
struct cmp{
bool operator () (const pair<ll, int> &a, const pair<ll, int> &b) const{
return a.first > b.first;
}
};
priority_queue<pair<ll, int>, vector< pair<ll, int> >, cmp> q;
void solve(){
cin >> n1 >> n2 >> n3 >> n4;
for(int i = 1; i <= n1; i++){
cin >> a[i];
}
for(int i = 1; i <= n2; i++){
cin >> b[i];
}
for(int i = 1; i <= n3; i++){
cin >> c[i];
}
for(int i = 1; i <= n4; i++){
cin >> d[i];
}
int m1;
cin >> m1;
for(int i = 1; i <= m1; i++){
int x, y;
cin >> x >> y;
vec[2][y].insert(x);
}
int m2;
cin >> m2;
for(int i = 1; i <= m2; i++){
int x, y;
cin >> x >> y;
vec[3][y].insert(x);
}
int m3;
cin >> m3;
for(int i = 1; i <= m3; i++){
int x, y;
cin >> x >> y;
vec[4][y].insert(x);
}
//cout << m1 << m2 << m3 << "\n";
memset(dp, 0x3f, sizeof dp);
for(int i = 1; i <= n1; i++){
dp[1][i] = a[i];
}
for(int tt = 2; tt <= 4; tt++){
//cout << tt << "\n";
if(tt == 2){
while(q.size()){
q.pop();
}
for(int i = 1; i <= n1; i++){
q.push({dp[1][i], i});
}
//cout << q.size() << "\n";
}
else if(tt == 3){
while(q.size()){
q.pop();
}
for(int i = 1; i <= n2; i++){
q.push({dp[2][i], i});
}
}
else{
while(q.size()){
q.pop();
}
for(int i = 1; i <= n3; i++){
q.push({dp[3][i], i});
}
}
vector< pair<ll, int> > tmp;
if(tt == 2){
for(int i = 1; i <= n2; i++){
tmp.clear();
while(q.size() != 0 && vec[tt][i].find((q.top().second)) != vec[tt][i].end()){
pair<ll, int> now = q.top();
q.pop();
tmp.push_back(now);
}
if(q.size() != 0){
pair<ll, int> now = q.top();
dp[tt][i] = min(dp[tt][i], now.first + b[i]);
}
for(int j = 0; j < tmp.size(); j++){
q.push(tmp[j]);
}
}
}
else if(tt == 3){
for(int i = 1; i <= n3; i++){
tmp.clear();
while(q.size() != 0 &&vec[tt][i].find((q.top().second)) != vec[tt][i].end()){
pair<ll, int> now = q.top();
q.pop();
tmp.push_back(now);
}
if(q.size() != 0){
pair<ll, int> now = q.top();
dp[tt][i] = min(dp[tt][i], now.first + c[i]);
}
for(int j = 0; j < tmp.size(); j++){
q.push(tmp[j]);
}
}
}
else{
for(int i = 1; i <= n4; i++){
tmp.clear();
while(q.size() != 0 &&vec[tt][i].find((q.top().second)) != vec[tt][i].end()){
pair<ll, int> now = q.top();
q.pop();
tmp.push_back(now);
}
if(q.size() != 0){
pair<ll, int> now = q.top();
dp[tt][i] = min(dp[tt][i], now.first + d[i]);
}
for(int j = 0; j < tmp.size(); j++){
q.push(tmp[j]);
}
}
}
}
ll ans = 0x3f3f3f3f3f3f3f3f;
for(int i = 1; i <= n4; i++){
ans = min(ans, dp[4][i]);
}
if(ans >= 0x3f3f3f3f3f3f3f3f){
cout << "-1" << "\n";
}
else{
cout << ans << "\n";
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/260326.html
標籤：其他