好好復習初賽，我壓線過的
瞎搞的封面
1.分糖果
一般來說T1都不會太難，其實他還是不是很難
我太蒻了，考場半小時才想出來
咳咳，一看資料范圍有有 10^9，一看就不是用暴力做的，
假如有n個小朋友（包括你），你搬了k塊糖果，那么你最終得到的獎勵就是 k mod n 塊糖果，也就是說，假如你最少搬l塊糖果，最多搬k塊糖果，你如果要得到最多的獎勵，就要在l到r之間選一個數，使得這個數模n的值最大，
那么最優的情況下會剩 n - 1 塊糖果，當然，樣例 2告訴我們，有時候我們沒法這么貪心，可能最優的結果達不到 n - 1，那么就說明，在l到r之間，數越大，模n的值就越大，所以對于這種情況，就直接拿r塊糖果，結果一定是最優的，而其他情況最優值就是n - 1，
那么，你們要的代碼來了：
#include<bits/stdc++.h>
using namespace std;
int n,l,r;
int main(){
cin>>n>>l>>r;
cout<<min(r,l+(n-1-l%n))%n; //先嘗試將余數補到n-1，如果超過r，那么結果就是r mod n，否則就是n-1
return 0;
}2.插入排序
T2也沒有多難，只是坑有點多，避開就好了
由于給的條件是修改次數不超過5000 ，我們應該在修改處做文章，
注意到一個陣列a進行“示范代碼”之后，數 ai? 在 aj? 之前的充要條件是以下兩者中成立一個：
-
?
<
-
且 i<j
考慮維護一個陣列b儲存各個數在陣列a中的相對排名，那么開始輸入a時進行統計（用以上兩條判斷）之后：
每進行一次操作 2 ，輸出? ，
每進行一次操作 1 ，即將修改成 v ，此時用 O(n) 遍歷陣列中的各個元素，如果某一個元素i滿足在陣列插入排序后原本在x之前，現在在x之后（仍然用兩條判定），因為i與陣列中其他數的相對位置沒有變化，使
增加一，
?減少一即可，另外一種情況同理，
上代碼
#include<bits/stdc++.h>
using namespace std;
int n,q,a[8005],b[8005],num,x,v,ans;
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
if(i==j||a[j]<a[i]||a[j]==a[i])b[i]++;
else b[j]++;
}//這里的b[i]就是第i個數在陣列a[i]中的排位
}
for(int i=0;i<q;i++)
{
scanf("%d",&num);
if(num==1)
{
scanf("%d%d",&x,&v);
for(int i=1;i<=n;i++)
{
if(i==x)continue;
if((a[i]<a[x]||a[i]==a[x]&&i<x)&&(a[i]>v||a[i]==v&&i>x))
{
b[i]++;b[x]--;
}
else if((a[i]>a[x]||a[i]==a[x]&&i>x)&&(a[i]<v||a[i]==v&&i<x))
{
b[i]--;b[x]++;
}
}
a[x]=v;
}
if(num==2)
{
scanf("%d",&x);
printf("%d\n",b[x]);
}
}
return 0;
}3.網路連接
作為T3，肯定是有些難度的，但想想還是沒那么難
看到需要由地址串映射到計算機編號，我們可以考慮使用 map，這里推薦使用用法基本相似但查詢、修改復雜度均為 O(1) 的 unordered_map（需要用到 C++11，若在本地無法編譯則要加上編譯選項），
思路
- 先判斷每臺計算機提供的地址串是否符合規范，若不符合，直接輸出
ERR； - 對于每臺服務器（
Server）提供的地址串，先在unordered_map中尋找該地址串是否已經建立映射（即是否已經有服務器提供相同地址串以建立連接），若已有則輸出FAIL，否則建立映射并輸出OK； - 對于每臺客戶機 （
Client）提供的地址串，先在unordered_map中尋找該地址串是否已經建立映射（即是否已經有服務器提供該地址串以建立連接），若已有則該客戶機可以加入連接，此時輸出建立連接的服務器的編號，否則該客戶機不能加入連接，輸出FAIL，
這里先簡單介紹一下 unordered_map ，unordered_map 本質上就像一個陣列，
只不過你可以自己定義鍵和值 （其實就是下標與它所對應的元素） 型別，
unordered_map<string,int> mp; 這樣你就有了一個可以用 string 型別映射到 int 型別的 unordered_map 陣列 mpmp ，
mp["hello"] = 532;這意味著在 mpmp 陣列里， \mathtt{"hello"}"hello" 對應著 \mathtt{532}532 ，
mp.count("hello");
mp.count("world");判斷該元素之前是否存在映射， 回傳值分別為1和0，map 的用法則與其相似，這里不再贅述，
判斷地址串是否存在的部分可以用 unordered_map 解決，那么整道題的重點則落在了如何判斷地址串是否規范上，
我們先列出地址串不符合規范的所有可能形式，
- 形如
a.b.c.d:e，其中整數a,b,c,d,e有一個數超過題目給定的范圍（即 0≤a,b,c,d 2550≤a,b,c,d≤255≤e≤655350），或有一個數含有前導 0，
針對這種情況，我們可以用如下的方法依次提取a,b,c,d,e并判斷其是否在規定范圍內，
bool check(string s)
{
int len = s.length();
long long tmp = 0;
for(int i=0;i<len;i++)
{
if(s[i]=='.'||s[i]==':')
{
if(0<=tmp&&tmp<=255) //判斷a,b,c,d是否符合規范
{
tmp = 0; //清零
continue;
}
else return false;
}
else if(s[i]<'0'||s[i]>'9') return false;
if(i&&!tmp&&s[i-1]=='0') return false; //這一行用來判斷前導0
tmp = tmp*10+s[i]-'0'; //讀取數字
}
if(0<=tmp&&tmp<=65535) return true; //判斷e是否符合規范
else return false;
}- 形如
a.b.c:d.e，其中字符.或:出現的順序不規范，
針對這種情況，我們可以用計數器分別記錄.和:出現的次數，判斷:出現時，.出現的次數是否為 3， -
int cnt1=0,cnt2=0,cnt3=0; for(int i=0;i<len;i++) { if(s[i]=='.'||s[i]==':') { if(s[i]=='.') cnt1++; else if(s[i]==':') cnt2++; if(cnt1<3&&cnt2) return false; //出現順序是否規范 /* 判斷a,b,c,d的范圍是否規范 */ } else if(s[i]<'0'||s[i]>'9') return false; /* 判斷前導0 以及提取數字 */ }
-
形如
a..b.c:e或a.b.c:.e，其中字符.或:連著出現，
這時候符號的數量符合規范，但數字的數量不符合規范，可以仿照情況2，用計數器記錄數字出現的次數，并在最后判斷字符和數字出現的次數是否符合規范， -
形如
.a.b.c:e或a.b.c.d:，其中字符.或:出現在地址串頭尾， 針對字符出現在頭的情況，我們可以在字符出現時判斷是否已有數字出現；針對字符出現在尾的情況，可以用情況3的方法來解決，
這兩種情況都需要加上數字的計數器，
int len = s.length();
long long tmp = 0;
int cnt1=0,cnt2=0,cnt3=0;
for(int i=0;i<len;i++)
{
if((i==0||(s[i-1]=='.'||s[i-1]==':'))&&s[i]>='0'&&s[i]<='9') cnt3++;
//如果當前為第一個位置或前一個為字符，并且這個位置為數字
if(s[i]=='.'||s[i]==':')
{
/*
統計字符出現的次數
*/
if(cnt1<3&&cnt2) return false; //出現順序是否規范
if(!cnt3) return false; //如果字符在第一個數字前出現
/*
判斷a,b,c,d的范圍是否規范
*/
}
else if(s[i]<'0'||s[i]>'9') return false;
/*
判斷前導0 以及提取數字
*/
}
if(cnt1!=3||cnt2!=1||cnt3!=5) return false; //判斷字符、數字出現的數量
/*
判斷e的范圍是否規范
*/將上述4種情況的解決方案拼在一起，就得到判斷地址串是否規范的函式，
Code
#include <bits/stdc++.h>
using namespace std;
int n;
unordered_map<string,int>address;
bool check(string s)
{
int len = s.length();
long long tmp = 0;
int cnt1=0,cnt2=0,cnt3=0;
for(int i=0;i<len;i++)
{
if((i==0||(s[i-1]=='.'||s[i-1]==':'))&&s[i]>='0'&&s[i]<='9') cnt3++;
//如果當前為第一個位置或前一個為字符，并且這個位置為數字
if(s[i]=='.'||s[i]==':')
{
if(s[i]=='.') cnt1++;
else if(s[i]==':') cnt2++;
//統計字符出現的次數
if(cnt1<3&&cnt2) return false; //出現順序是否規范
if(!cnt3) return false; //如果字符在第一個數字前出現
if(0<=tmp&&tmp<=255) //判斷a,b,c,d的范圍是否規范
{
tmp = 0;
continue;
}
else return false;
}
else if(s[i]<'0'||s[i]>'9') return false; //出現了奇怪的字符
if(i&&!tmp&&s[i-1]=='0') return false; //判斷前導 0
tmp = tmp*10+s[i]-'0'; //提取數字
}
if(cnt1!=3||cnt2!=1||cnt3!=5) return false; //字符和數字出現的數量是否正確
if(0<=tmp&&tmp<=65535) return true; //判斷e的范圍
else return false;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
string cpt,adr;
cin>>cpt>>adr;
if(!check(adr)) puts("ERR"); //如果地址串不符合規范
else if(cpt=="Server")
{
if(address.count(adr)) puts("FAIL");
else
{
address[adr] = i;
puts("OK");
}
}
else if(cpt=="Client")
{
if(address.count(adr)) printf("%d\n",address[adr]);
else puts("FAIL");
}
}
return 0;
}4.小熊的果籃
T4我覺得比T3還水
首先對輸入序列建雙向鏈表，維護每一個“假塊”頭建雙向鏈表，共維護兩個鏈表，
這里的“假塊”指每個“假塊”中水果種類必定相同，但相鄰“假塊”中水果種類可能相同，
我們可以使用雙向鏈表的洗掉元素來模擬吃一個水果，
不斷回圈遍歷“假塊”頭鏈表，遍歷程序中記錄上一個被吃水果種類，遍歷到某個塊頭時，若其指向的水果與上一個被吃水果種類相同，直接將這個塊頭洗掉，相當于合并塊；若不同，吃掉這個水果，更新上一個被吃水果種類，將這個塊頭指向的水果變成被吃水果的下一個水果，
關于一個假塊被吃完的處理方法，此時這個假塊的塊頭一定會指向下一個塊頭，若這個塊頭的種類與被吃水果的種類不同，刪掉這個塊，因為遍歷下一個塊時將會吃掉這個水果；若相同，不動，因為接下來的程序將會把下一個塊的塊頭洗掉，這樣保證遍歷時不會出現長度小于一的假塊，若假塊沒有被吃完，其指向的下一個水果一定與吃掉的種類相同，同樣不做任何處理，
每個水果被遍歷一次，每個塊被洗掉一次，時間復雜度Θ(n)，
代碼如下：
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int MAXN = 2e5+10;
struct Node{
int prev;
int val;
int next;
};
int n;
int shuiguo[MAXN];
Node headList[MAXN];
Node shuiguoList[MAXN];
int cc;
void EatOne(int pos) {
int prev = shuiguoList[pos].prev;
int next = shuiguoList[pos].next;
shuiguoList[prev].next = next;
shuiguoList[next].prev = prev;
printf("%d ", pos);
}
void Del(int pos) {
int prev = headList[pos].prev;
int next = headList[pos].next;
headList[prev].next = next;
headList[next].prev = prev;
}
void Chi() {
int solo = headList[0].next;
int nowcolor = shuiguo[headList[solo].val];
while (solo!=cc+1) {
if (shuiguo[headList[solo].val]!=nowcolor) {
Del(solo);
solo = headList[solo].next;
continue;
}
EatOne(headList[solo].val);
headList[solo].val = shuiguoList[headList[solo].val].next;
if (shuiguo[headList[solo].val]!=nowcolor) {
Del(solo);
}
solo = headList[solo].next;
nowcolor^=1;
}
putchar('\n');
}
int main() {
scanf("%d", &n);
shuiguoList[0].next = 1;
for (int i = 1; i <= n; i++) {
scanf("%d", &shuiguo[i]);
shuiguoList[i].prev = i-1;
shuiguoList[i].next = i+1;
}
shuiguo[0] = 2;
shuiguo[n+1] = 2;
headList[0].next = 1;
for (int i = 1; i <= n; i++) {
if (shuiguo[i]!=shuiguo[i-1]) {
cc++;
headList[cc].prev = cc-1;
headList[cc].next = cc+1;
headList[cc].val = i;
}
}
while (shuiguoList[0].next!=n+1) {
Chi();
}
return 0;
}好好學初賽，我覺得初賽比復賽都難
初賽祝您上七十，復賽祝您AK，加油
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/385593.html
標籤：其他
上一篇：[Linux從無到有] 行程