今天，打了一下北郵周行算協的寒假比賽，我只是隨便打打，就打了一下第二賽道，據說是codeforces div3難度，大約花了差不多3小時，過了9題（一共10題），H題是一個位運算題，我是拆位考慮的，結合一下貪心思想，調了一個小時，始終不能通過，決定還是等一下那個題的題解吧，我就簡單講解一下我通過的9道題，
題目鏈接: http://zxoj.top:81/contest/1
A. 等引數列
思路：給你等引數列的前兩項，和項數，求等引數列的和，直接使用等引數列求和公式，注意開long long，
#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;
ll a, b, n;
int main(){
cin >> a >> b >> n;
ll d = b - a;
ll c = a + d*(n - 1);
ll ans = (a + c)*n/2;
cout << ans << "\n";
return 0;
}
B. 士兵選擇
思路：資料量比較小，直接開 O ( n 2 ) O(n^2) O(n2)暴力就好了，
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
int n, d;
int a[1010];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> d;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
int ans = 0;
for(int i = 1; i <= n; i++){
for(int j = i+1; j <= n; j++){
if(abs(a[i] - a[j]) <= d){
if(i == j)
ans++;
else
ans += 2;
}
}
}
cout << ans << "\n";
return 0;
}
C. 遞增序列
思路：一次只能加d，最少加多少次讓序列嚴格單調遞增，貪心思想，如果這個數小于等于上一個數才需要加，具體加多少次，要注意細節，
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll d;
ll a[2010];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> d;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
ll ans = 0;
for(int i = 2; i <= n; i++){
if(a[i] > a[i-1]){
continue;
}
ll tmp = a[i-1] - a[i];
ll now = tmp / d + 1;
ans += now;
a[i] += d*now;
}
cout << ans << "\n";
return 0;
}
D. Easy Problem
思路：找規律，如果字串字符數目是1，是yes，如果字串數量大于1，并且有一個字符出現了兩次及以上，是yes，否則就是no，
#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 cnt[30];
string s;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> s;
if(s.length() == 1){
cout << "YES" << "\n";
return 0;
}
for(int i = 0; i < s.length(); i++){
cnt[s[i]-'a']++;
}
int ok = 0;
for(int i = 0; i < 26; i++){
if(cnt[i] > 1){
ok = 1;
break;
}
}
if(ok){
cout << "YES" << "\n";
}
else{
cout << "NO" << "\n";
}
return 0;
}
E. 數列
思路：直接模擬就行，注意好上一個01分界點，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 n, m;
int vis[100010];
int change[100010];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> m;
cin >> n;
for(int i = 1; i <= m; i++){
cin >> vis[i] >> change[i];
}
int last0 = -1, last1 = -1;
int max0 = 0, max1 = 0;
if(change[1]){
last1 = vis[1];
}
else{
last0 = vis[1];
}
for(int i = 2; i <= m; i++){
if(change[i] && change[i-1]){
}
else if(change[i] && !change[i-1]){
if(last0 != -1){
max0 = max(max0, vis[i] - last0);
}
last1 = vis[i];
last0 = -1;
}
else if(!change[i] && change[i-1]){
if(last1 != -1){
max1 = max(max1, vis[i] - last1);
}
last0 = vis[i];
last1 = -1;
}
else{
}
}
if(change[m]){
max1 = max(max1 , n - last1 + 1);
}
else{
max0 = max(max0, n - last0 + 1);
}
cout << max1 << " " << max0 << "\n";
return 0;
}
F. DNA
這個題n是100000，直接 O ( n 2 ) O(n^2) O(n2)暴力過不了，考慮優化成 O ( n l o g n ) O(nlogn) O(nlogn)，我們發現，一個字串的最多20個字符，我們可以從這里入手，我們要預處理出題里所有的字串，以及一個字串出現了幾次，需要對字串進行重新編號，我們求出答案的時候，遍歷到一個字串，只需要看它的配對字串在題目中出現了幾次就好，我們可以將以上操作用哈希實作，比較高效，C++用map類就行，
#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;
string s[100010];
int n;
map<string, int> cnt;
map<string, int> id;
string t[100010];
int vis[100010];
int tot = 0;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> s[i];
if(id.find(s[i]) == id.end()){
id[s[i]] = ++tot;
cnt[s[i]]++;
t[tot] = s[i];
}
else{
cnt[s[i]]++;
}
}
ll ans = 0;
for(int i = 1; i <= tot; i++){
if(!vis[i]){
//cout << i << "\n";
string tmp = t[i];
string mat = "";
for(int i = 0; i < tmp.length(); i++){
if(tmp[i] == 'A'){
mat += 'T';
}
else if(tmp[i] == 'T'){
mat += 'A';
}
else if(tmp[i] == 'C'){
mat += 'G';
}
else{
mat += 'C';
}
}
//cout << tmp << " " << mat << "\n";
if(id.find(mat) == id.end()){
}
else{
ans += 1ll*min(cnt[mat], cnt[tmp]);
vis[id[mat]] = 1;
}
vis[i] = 1;
}
}
cout << ans << "\n";
return 0;
}
G. 三棱錐
思路：dp，我們設一個陣列dp[n][m]表示第n步之后到m的方案數，假設三棱錐的四個點是0，1，2，3，開始時候，在三棱錐的0點處, 所以dp[0][0] = 1，我們規劃出dp[n][0]就是答案，
dp[i][0] = ((dp[i-1][1] + dp[i-1][2])%mod + dp[i-1][3])%mod;
dp[i][1] = ((dp[i-1][0] + dp[i-1][2])%mod + dp[i-1][3])%mod;
dp[i][2] = ((dp[i-1][1] + dp[i-1][0])%mod + dp[i-1][3])%mod;
dp[i][3] = ((dp[i-1][1] + dp[i-1][2])%mod + dp[i-1][0])%mod;
#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;
const int mod = 1e9 + 7;
int dp[10000001][4];
int n;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
dp[0][0] = 1;
for(int i = 1; i <= n; i++){
dp[i][0] = ((dp[i-1][1] + dp[i-1][2])%mod + dp[i-1][3])%mod;
dp[i][1] = ((dp[i-1][0] + dp[i-1][2])%mod + dp[i-1][3])%mod;
dp[i][2] = ((dp[i-1][1] + dp[i-1][0])%mod + dp[i-1][3])%mod;
dp[i][3] = ((dp[i-1][1] + dp[i-1][2])%mod + dp[i-1][0])%mod;
}
cout << dp[n][0]%mod << "\n";
return 0;
}
I. Hard Problem I
思路：貪心，如果s[i] = s[i-1]，我們讓s[i]變成’#’，ans++，就可以得出答案，因為，一個字符能否構成兩個連續相同字符，之和s[i-1]，s[i+1]，有關，如果s[i] = s[i-1], 無論s[i+1]是什么，我們都可以保證s[i]進行修改之后，不等于s[i+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;
string s;
int cnt;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> s;
for(int i = 1; i < s.length(); i++){
if(s[i] == s[i-1]){
s[i] = '#';
cnt++;
}
}
cout << cnt << "\n";
}
J. 訊息傳播
思路：這題是一個思維題，i知道訊息，下一天所有
g
c
d
(
i
+
1
,
j
+
1
)
=
1
gcd(i+1, j+1) = 1
gcd(i+1,j+1)=1的都會知道訊息，我們把原序列中的i都+1，k也+1，題目就是
2
,
3
,
4
,
,
,
,
n
+
1
2,3,4,,,,n+1
2,3,4,,,,n+1人，第0天k+1知道訊息，問第幾天所有人都知道訊息，
我們肯定要對k+1這個數進行因數分解，我們可以知道a，和（a+1或者 a-1)的因數除了1以外都是不同的，因為不存在i, i+1同時被k整除且k != 1，所以第0天k+1,知道訊息，第一天k+2，k就一定知道訊息，而第一天不能接受訊息的，第二天都可以通過k, k+2知道訊息，所以本題的最終答案要么是1，要么是2，
所以，我們只要在最多
O
(
n
)
O(\sqrt{n})
O(n
?)，找到k+1這個數除了1以外的最小因子m就行，如果2*m > n，就是這個序列中所有數和k+1的最大公因數是1，就需要1天，否則需要2天，
#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;
ll n, k;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
n++;
k++;
int ok = 0;
ll now = 1;
for(ll i = 2; i * i <= k; i++){
if(k % i == 0){
ok = 1;
now = i;
break;
}
}
if(!ok){
now = k;
}
if(now*2 > n){
cout << "1" << "\n";
}
else{
cout << "2" << "\n";
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/256442.html
標籤：其他
上一篇：仿頭條方形進度條
下一篇：C語言實作三子棋小游戲