C題 1480C
一個互動題，題目給你一個n代表陣列長度，然后詢問該陣列的谷底，也就是存在一個pos 他兩邊相鄰的值都大于他，如果當前pos的值沒有給出，就輸入它，劃重點 ，不超過100次找出來，那么顯然就是二分了 ，
分析： 我們二分mid 作為谷底，那么如果 a[mid]<a[mid-1] 要構成谷底就要往右邊找，所以 l= mid 這樣子二分 很easy
int a[222222];
inline int check(ll p) {
if(a[p]) return a[p];
printf("? %lld\n", p), fflush(stdout);
scanf("%lld", &a[p]); return a[p];
}
signed main()
{
ll n;
read(n);
a[0] = a[n + 1] =1e18;
int l = 1, r = n;
while(l < r)
{
ll mid = l + r + 1 >> 1;
if(check(mid) < check(mid - 1))
l = mid;
else
r = mid - 1;
}
printf("! %lld\n", l);
fflush(stdout);
}
1480 D1
題意：給我們一個長度為n的序列，現在可以染色黑白，抽出來形成a0序列和a1序列，現在合并相鄰的相同值，最終序列剩下的元素個數就是貢獻，D1詢問我們最大貢獻，D2詢問我們最小貢獻，先考慮下最大貢獻，那必然是盡可能的使得a0 序列 a1 序列相鄰位不相同，那么我們維護兩個序列s1 ,s2 只需要記錄他們的末尾元素即可 不妨令s1 =a[1] 那么維護程序從i=2開始遍歷陣列，詳情看代碼，分類討論下ai放在s1還在s2 即可
ll a[111111];
ll vis[111111];
ll op[50];
signed main(){
ll n;
read(n);
ll num_1=0;
ll num_ma=0;
for(int i=1;i<=n;i++){
read(a[i]);
vis[a[i]]++;
}
op[1]=a[1];
ll cnt=1;
for(int i=2;i<=n;i++){
if(a[i]!=op[1]){
cnt++;// 可以放
if(op[1]!=a[i+1]&&a[i]!=op[2]){
// 可放1 也可放2 優先照顧2
op[2]=a[i];
}
else{
op[1]=a[i];
}
}
else if(a[i]!=op[2]){
cnt++;
op[2]=a[i];
}
}
printf("%lld\n",cnt);
}
1480D2 求min
這個題就要盡可能的把相同的值堆在一起 ，我們先給每個連續段歸為1 ，例如12222223 歸為123
然后開始遍歷，打標記，當還沒有遇到重復標記 的點時，遇到一個沒有標記過的數貢獻就+1. 如果遇到了標記相同的數 比如樣例
7
1 2 3 1 3 2 2
（我先演示一遍
合并一下變為序列1 2 3 1 3 2
然后1 2 3 獨立標記后 1重復標記 之前我們的操作相當于每次分別往s1 s2序列丟進去一個值 那么到了 pos=4 1標記重復 此時
s1 : 1 3 1 _待定
s2: 2
那么我們清空標記陣列 并且把 1,3 標記 把3 丟在s2 里面 于是
s1:1 1 2
s2:2 3 3
于是總貢獻為 4
ll a[111111];
ll vis[111111];
ll op[50];
vector<ll>s;
map<ll,ll>sb;
signed main(){
ll n;
read(n);
ll num_1=0;
ll num_ma=0;
a[n+1]=0;
for(int i=1;i<=n;i++){
read(a[i]);
vis[a[i]]++;
}
for(int i=1;i<=n;i++){
if(a[i]!=a[i+1]){
s.push_back(a[i]);
}
}
ll ans=0;
for(int i=0;i<s.size();i++){
if(sb[s[i]]==0){
ans++;
sb[s[i]]++;
}
else{
sb.clear();
sb[s[i]]++;
sb[s[i-1]]++;
}
}
printf("%lld",ans);
感覺挺簡單的 qwq 下午SAM沖沖沖
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/258051.html
標籤：其他