牛客練習賽88游記
牛客練習賽88游記
A - 活著的證據
題目大意：
將一個各數位都為 \(1\sim 8\) 的數逐位寫成羅馬數字，可以得到一個僅包含字符 V 和 I 的串。
其中阿拉伯數字 \(1\sim 8\) 對應的羅馬數字如下：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|
I |
II |
III |
IV |
V |
VI |
VII |
VIII |
求使用不超過 \(S_V\) 個 V，不超過 \(S_I\) 個 I，能表示出不超過 \(N\) 位的最大數是多少？ |
|||||||
| \(\sum N\le 5\times 10^6\) |
思路：
貪心。
顯然 \(4\) 不可能出現，因為用 \(6\) 來取代更加劃算。
將 V 盡量安排在高位。若 \(S_V < N\)，則再將剩下的空位先用一個 I 來填上。
如果還有多余的 I，則盡量往前放，能放滿 \(3\) 個就放 \(3\) 個，否則就放 \(2\) 個或者 \(1\) 個，直到 I 用完或者放不下更多 I 為止。
時間復雜度 \(\mathcal O(N)\)。
源代碼：
#include<cstdio>
#include<cctype>
#include<algorithm>
inline int getint() {
char ch;
while(!isdigit(ch=getchar()));
int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
const int N=5e6+1;
int v[N],i[N];
int main() {
for(int T=getint();T;T--) {
int V=getint(),I=getint();
int n=std::min(V+I,getint());
std::fill(&v[1],&v[n]+1,0);
std::fill(&i[1],&i[n]+1,0);
for(int j=1;j<=std::min(V,n);j++) v[j]++;
for(int j=V+1;j<=n;j++) i[j]++;
I-=std::max(n-V,0);
for(int j=1;j<=n;j++) {
if(I==0) break;
if(I==1) {
i[j]+=1;
I-=1;
} else if(I==2||i[j]==1) {
i[j]+=2;
I-=2;
} else {
i[j]+=3;
I-=3;
}
}
for(int j=1;j<=n;j++) {
putchar('0'+v[j]*5+i[j]);
}
puts("");
}
}
B - 尋尋覓覓尋不到
題目大意：
給定兩個串 \(M\)、\(C\) 和一個整數 \(K\)。
問是否可以從 \(M\) 中選取某個長度為 \(K\) 的子串并將其位置移到末尾，使得到的新串與 \(C\) 相等。
\(\sum|M|,\sum|C|\le 3\times 10^5; 1\le K\le 6\)。
思路：
基礎的字符串哈希題。
顯然若 \(|M|\ne |C|\) 則答案肯定是 NO。
當 \(|M|=|C|\) 時可對兩串分別進行哈希。由于 \(C\) 確定，則長度為 \(K\) 的子串確定。枚舉該子串出現的位置，對兩部分分別比較哈希值即可。
\(K\) 的范圍限制似乎是不必要的。
時間復雜度 \(\mathcal O(\sum |M|+\sum |C|)\)。
源代碼：
#include<cstdio>
#include<cctype>
#include<cstring>
inline int getint() {
char ch;
while(!isdigit(ch=getchar()));
int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
using uint64=unsigned long long;
constexpr int N=5e6+2;
constexpr uint64 base=233;
char s[N],t[N];
uint64 pwr[N],hashs1[N],hashs2[N];
inline uint64 gethash(const int &l,const int &r) {
uint64 ret=0;
for(int i=l;i<=r;i++) {
ret=ret*base+s[i];
}
return ret;
}
int main() {
pwr[0]=1;
for(int i=1;i<=N-2;i++) {
pwr[i]=pwr[i-1]*base;
}
for(int T=getint();T;T--) {
scanf("%s %s",&s[1],&t[1]);
int k=getint();
const int n=strlen(&s[1]);
if(n!=strlen(&t[1])) {
puts("NO");
continue;
}
uint64 hash1=0,hash2=0;
for(int i=1;i<=n-k;i++) {
hash1=hash1*base+t[i];
}
for(int i=n-k+1;i<=n;i++) {
hash2=hash2*base+t[i];
}
for(int i=1;i<=n;i++) {
hashs1[i]=hashs1[i-1]*base+s[i];
}
hashs2[n+1]=0;
for(int i=n;i>=1;i--) {
hashs2[i]=hashs2[i+1]+s[i]*pwr[n-i];
}
for(int i=1;i<=n-k+1;i++) {
if(gethash(i,i+k-1)==hash2) {
if(hashs1[i-1]*pwr[n-i-k+1]+hashs2[i+k]==hash1) {
puts("YES");
goto Next;
}
}
}
puts("NO");
Next:;
}
}
C - 踩不出足跡
題目大意：
有 \(n\) 個 \(k\) 位二進制數。在相鄰兩數之間插入異或、同或運算符，使得最終結果最大。
\(n\le 10^6; k\le 64\)。
思路：
同或相當于對異或結果逐位取反。
對于僅含取反、異或操作的算式，局部取反等于全局取反。
因此我們只需無腦將這些數全部異或起來，最后決定是否需要取反即可。
另外注意 \(k=64\) 時會爆 unsigned long long，需特判。
時間復雜度 \(\mathcal O(n)\)。
源代碼：
#include<cstdio>
#include<cctype>
#include<algorithm>
using uint64=unsigned long long;
inline uint64 getint() {
char ch;
while(!isdigit(ch=getchar()));
uint64 x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
int main() {
const int n=getint(),k=getint();
uint64 ans=0;
for(int i=1;i<=n;i++) {
ans^=getint();
}
if(k!=64) {
printf("%llu\n",std::max(ans,(1llu<<k)-1-ans));
} else {
printf("%llu\n",std::max(ans,~ans));
}
}
D - 都市的柏油路太硬
題目大意：
一張 \(n\) 個點、\(m\) 條邊的連通雙向圖，定義一條路徑的權值為該路徑最長邊的長度，點對的權值為兩點間所有路徑權值的最小值。
以所有點對間的權值為邊權，建立 \(n\) 個點、\(\frac{n(n-1)}{2}\) 條邊的新圖，并由該圖建立最小生成樹。
\(q\) 次詢問，每次詢問最小生成樹上兩點間最大邊權。
\(n\le 10^5; m\le 5\times 10^5; q\le 10^7\)。
三倍經驗：
思路：
仔細分析題意后不難發現所求即是原圖所對應 Kruskal 重構樹中兩點 LCA 的權值。注意到 \(q\le 10^7\) 因此使用倍增或樹剖求 LCA 容易 TLE，需要用 Tarjan 離線求 LCA。
時間復雜度 \(\mathcal O(m\log m+n\cdot\alpha(n)+n+q)\)。
源代碼：
#include<cstdio>
#include<cctype>
#include<vector>
#include<numeric>
#include<algorithm>
using uint64=unsigned long long;
inline uint64 getint() {
char ch;
while(!isdigit(ch=getchar()));
uint64 x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
typedef unsigned long long ull;
ull myRand(ull &k1, ull &k2){
ull k3 = k1, k4 = k2;
k1 = k4;
k3 ^= (k3 <<23);
k2 = k3 ^ k4 ^ (k3 >>17) ^ (k4 >>26);
return k2 + k4;
}
std::pair<int,int>myRanq(ull&k1,ull&k2,int MAXN){
int x=myRand(k1,k2)%MAXN+1,y=myRand(k1,k2)%MAXN+1;
if(x>y)return std::make_pair(y,x);
else return std::make_pair(x,y);
}
constexpr int N=2e5+1,logN=18,M=5e5+1;
struct Edge {
int u,v,w;
bool operator < (const Edge &rhs) const {
return w<rhs.w;
}
};
Edge edge[M];
int n,m;
int val[N];
int par[N],dep[N]={-1},anc[N][logN];
std::vector<int> e[N];
inline void add_edge(const int &u,const int &v) {
e[u].emplace_back(v);
anc[v][0]=u;
}
struct DisjointSet {
int anc[N];
int find(const int &x) {
return x==anc[x]?x:anc[x]=find(anc[x]);
}
inline void init(const int &n) {
std::iota(&anc[1],&anc[n]+1,1);
}
inline bool same(const int &x,const int &y) {
return find(x)==find(y);
}
inline void merge(const int &x,const int &y) {
anc[find(x)]=find(y);
}
};
DisjointSet djs;
std::vector<int> q[N];
bool vis[N];
int ans=0;
void tarjan(const int &x) {
for(int &y:e[x]) {
tarjan(y);
djs.merge(y,x);
}
for(int &y:q[x]) {
if(!vis[y]) continue;
ans^=val[djs.find(y)];
}
vis[x]=true;
}
int main() {
n=getint(),m=getint();
for(int i=1;i<=m;i++) {
edge[i].u=getint();
edge[i].v=getint();
edge[i].w=getint();
}
std::sort(&edge[1],&edge[m]+1);
djs.init(n*2-1);
int t=n;
for(int i=1;i<=m;i++) {
const int u=djs.find(edge[i].u);
const int v=djs.find(edge[i].v);
const int &w=edge[i].w;
if(u==v) continue;
val[++t]=w;
add_edge(t,u);
add_edge(t,v);
djs.merge(u,t);
djs.merge(v,t);
}
const int q=getint();
uint64 a1=getint(),a2=getint();
for(int i=0;i<q;i++) {
const auto q=myRanq(a1,a2,n);
::q[q.first].emplace_back(q.second);
::q[q.second].emplace_back(q.first);
}
djs.init(t);
tarjan(t);
printf("%d\n",ans);
}
浙公網安備 33010602011771號