Codeforces Round #637 (Div. 2) A~D
http://codeforces.com/contest/1341/
A. Nastya and Rice
題意
有 \(n\) 個范圍在 \([a-b,a+b]\) 的數字，詢問他們的和能否在區間 \([c-d,c+d]\) 內，
解題
這 \(n\) 個數字和的范圍是 \([n(a-b),n(a+b)]\) ，判斷是否與 \([c-d,c+d]\) 存在交集即可，
def scanf():
return list(map(int,input().split()))
for t in range(int(input())):
n,a,b,c,d = scanf()
p = n*(a-b); q = n*(a+b)
if(p>c+d or q<c-d): print("NO")
else: print("YES")
B. Nastya and Door
題意
給定一個正整數序列，代表連綿的山脈，序列中如果存在 \(a_{i-1}<a_i \land a_i>a_{i+1}\) 的位置，則稱 \(a_i\) 為山峰，
有一個巨大的門，把這個門水平扔山上問最多能分成幾份，這個門或門的碎片，遇到山峰之后就會分成兩半，
解題
這個題是真的難翻譯，又長又玄幻，不過題目還算簡單，
差分，記錄位置前面的山峰數量，尋找山峰最多的區間，在這里把門扔下去分成的份數最多，為山峰數\(+1\) ，
注意下邊界的判定，題目中說區間邊界的山峰不會分割門，
#include<bits/stdc++.h>
#define ll long long
#define fr(i,n) for(int i=0;i<n;i++)
#define frs(i,n,flag) for(int i=0;i<n&&flag;i++)
#define frr(i,j,n) for(int i=j;i<n;i++)
#define r_frr(i,j,n) for(int i=n-1;i>=j;i--)
#define frrs(i,j,n,flag) for(int i=j;i<n&&flag;i++)
#define r_frrs(i,j,n,flag) for(int i=n-1;i>=j&&flag;i--)
#define arend(i,n) ((i!=n-1)?" ":"\n")
#define memset0(dp) memset(dp,0,sizeof(dp))
#define print_arr(begin,end) for(auto it = begin;it!=end;it++) cout<<*it<<arend(it,end);
#define log_this(name,value) cout<<name<<": "<<value<<endl;
#define e4 10004
#define e5 100005
#define e6 1000006
#define e7 10000007
#define e9 1000000000
#define INF 9999999
using namespace std;
int to_int(string s) {stringstream ss;ss<<s;int a;ss>>a;return a;}
string to_str(double a) {stringstream ss;ss<<a;return ss.str();}
int a[2*e5];
int ct[2*e5]; //記錄區間 (0,i) 的山峰數量，注意是開區間
int main(){
cin.tie(0);
//ios::sync_with_stdio(false);
//cout<<setiosflags(ios::fixed)<<setprecision(0);
//freopen("1.out","w",stdout);
int t;
while(cin>>t){
while(t--){
int n,k;cin>>n>>k;
fr(i,n) cin>>a[i];
ct[0] = 0;
ct[1] = 0;
frr(i,1,n-1){
ct[i+1] = ct[i];
if(a[i]>a[i-1]&&a[i]>a[i+1]){
ct[i+1]++;
}
}
ct[n] = ct[n-1];
int ans = -1;
int l = 0;
frr(i,0,n-k+1){
if(ans<ct[i+k-1]-ct[i+1]){
l = i;
ans = ct[i+k-1] - ct[i+1];
}
}
cout<<ans+1<<" "<<l+1<<endl;
}
}
return 0;
}
C. Nastya and Strange Generator
題意
有一個隨機的數字生成器，按照如下生成規則，
-
第 \(i\) 次操作將數字 \(i\) 按照下面規則填入；
-
\(r_j\) 表示位置 \(j\) 之后的第一個為空的位置；
-
\(count_t\) 表示位置 \(t\) 被其他位置選做 \(r_j\) 的次數，即 \(r.count(t)\)；
-
每次只能選取 \(count_t\) 最大的位置填入 \(i\) ；
-
如果有多個相同的最大值，則可以從中選取任意一個，
給定一個由 \(n\) 個不同數字組成的陣列，詢問能否使用該生成器生成，
解題
這個題也是題面不是很友好，讀題面和理解題意用了很長時間，在50分鐘的時候過題沒想到還能排到1900，說明很多人都被這題面卡住了（絕了
通過舉例模擬填充程序發現，填充機制很簡單，一旦選取位置 \(t\) 填充數字 \(i\) ，那么位置 \(t+1\) 一定是序列中 \(count\) 值最大的，所以我們的 \(i+1\) 必須填充到位置 \(t+1\) 上，以此類推，直至位置被已被填充或者到達末尾，最后得到的填充序列一定滿足以下兩個條件：
- 由每小段連續遞增子序列組成；
- 前面的連續遞增子序列的元素一定大于后面連續子序列的元素，
判斷輸入序列是否同時滿足上面兩個條件即可，
#include<bits/stdc++.h>
#define ll long long
#define fr(i,n) for(int i=0;i<n;i++)
#define frs(i,n,flag) for(int i=0;i<n&&flag;i++)
#define frr(i,j,n) for(int i=j;i<n;i++)
#define r_frr(i,j,n) for(int i=n-1;i>=j;i--)
#define frrs(i,j,n,flag) for(int i=j;i<n&&flag;i++)
#define r_frrs(i,j,n,flag) for(int i=n-1;i>=j&&flag;i--)
#define arend(i,n) ((i!=n-1)?" ":"\n")
#define memset0(dp) memset(dp,0,sizeof(dp))
#define print_arr(begin,end) for(auto it = begin;it!=end;it++) cout<<*it<<arend(it,end);
#define log_this(name,value) cout<<name<<": "<<value<<endl;
#define e4 10004
#define e5 100005
#define e6 1000006
#define e7 10000007
#define e9 1000000000
#define INF 9999999
using namespace std;
int to_int(string s) {stringstream ss;ss<<s;int a;ss>>a;return a;}
string to_str(double a) {stringstream ss;ss<<a;return ss.str();}
int a[1*e5];
int main(){
cin.tie(0);
//ios::sync_with_stdio(false);
//cout<<setiosflags(ios::fixed)<<setprecision(0);
//freopen("1.out","w",stdout);
int t;
while(cin>>t){
while(t--){
int n;cin>>n;
fr(i,n) cin>>a[i];
int lastw = -1;
int noww = a[n-1];
bool can = true;
r_frr(i,1,n){
if(a[i-1]>a[i]){
if(a[i]<lastw){
can = false;
break;
}
lastw = noww;
noww = a[i-1];
}else{
if(a[i]-a[i-1]>1){
can = false;
break;
}
}
}
if(can) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
return 0;
}
D. Nastya and Scoreboard
題意
有一個由火柴棍拼圖組成的序列，詢問加上 \(k\) 根火柴棍能夠拼出的最大數字是多少，
解題
首先題面中有兩個事情需要注意：
- 輸入拼圖序列中存在非數字的情況；
- \(k\) 個火柴可能不能夠剛好讓所有的拼圖變成數字，
貪心+dfs，從大到小搜索可行情況，注意這里要用記搜，不然會超時，
既然記搜可過，看這個資料范圍，估計也有dp的解法，等有時間再補上（挖坑+1
#include<bits/stdc++.h>
#define ll long long
#define fr(i,n) for(int i=0;i<n;i++)
#define frs(i,n,flag) for(int i=0;i<n&&flag;i++)
#define frr(i,j,n) for(int i=j;i<n;i++)
#define r_frr(i,j,n) for(int i=n-1;i>=j;i--)
#define frrs(i,j,n,flag) for(int i=j;i<n&&flag;i++)
#define r_frrs(i,j,n,flag) for(int i=n-1;i>=j&&flag;i--)
#define arend(i,n) ((i!=n-1)?" ":"\n")
#define memset0(dp) memset(dp,0,sizeof(dp))
#define print_arr(begin,end) for(auto it = begin;it!=end;it++) cout<<*it<<arend(it,end);
#define log_this(name,value) cout<<name<<": "<<value<<endl;
#define e4 10004
#define e5 100005
#define e6 1000006
#define e7 10000007
#define e9 1000000000
#define INF 9999999
using namespace std;
int to_int(string s) {stringstream ss;ss<<s;int a;ss>>a;return a;}
string to_str(double a) {stringstream ss;ss<<a;return ss.str();}
int n,k;
int ans[2005];
int cost[2005][10];
int preCan[2005][2005]; //記錄[i+1,n)的元素能否使用j完美填充,-1未訪問，0否，1是
string ITB[] = {
"1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"
};
int Cost(string org,string nto){
int cost = 0;
fr(i,7){
int p = nto[i]-org[i];
if(p<0){
cost = -1;
break;
}else{
cost+=p;
}
}
return cost;
}
bool dfs(int i,int k){
if(i==n&&k==0) return preCan[i][k] = true;
if(k<0 ||(i==n&&k>0)) return preCan[i][k] = false;
r_frr(j,0,10){
if(cost[i][j]!=-1){
//cout<<i<<" "<<j<<" "<<cost[i][j]<<endl;
ans[i] = j;
bool hasf;
int left = k-cost[i][j];
if(preCan[i+1][left]==-1) hasf = dfs(i+1,left);
else hasf = preCan[i+1][left];
if(hasf) return preCan[i][k] = hasf;
}
}
return preCan[i][k] = false;;
}
int main(){
cin.tie(0);
//ios::sync_with_stdio(false);
//cout<<setiosflags(ios::fixed)<<setprecision(0);
while(cin>>n>>k){
string inp;
fr(i,n){
cin>>inp;
fr(j,10) cost[i][j] = Cost(inp,ITB[j]);
}
fr(i,n+1) fr(j,k+1) preCan[i][j] = -1;
bool hasf = dfs(0,k);
if(hasf){
fr(i,n) cout<<ans[i];
cout<<endl;
}else{
cout<<"-1"<<endl;
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/55355.html
標籤：其他
下一篇：三維凸包