[Codeforces Round 857 (Div. 1)][Codeforces 1801A~1801G（部分，已更新A~D、F）]
FST哩，好似！本來能+80的，現(xiàn)在只加了30，相當(dāng)于掉了50分捏
1801A - The Very Beautiful Blanket
題目大意：要求構(gòu)造一個 \(n\times m\) 的矩陣 \(B\)，使得對任意一個 \(4\times 4\) 的子矩陣 \(A\) 均滿足 \(A_{13} \oplus A_{14} \oplus A_{23} \oplus A_{24} = A_{31} \oplus A_{32} \oplus A_{41} \oplus A_{42}\) 且 \(A_{13} \oplus A_{14} \oplus A_{23} \oplus A_{24} = A_{31} \oplus A_{32} \oplus A_{41} \oplus A_{42}\)
直接令 \(A_{ij}=256\times i+j\) 即可，原理是這樣構(gòu)造可以讓任意一個 \(2\times 2\) 的子矩陣滿足異或和為零，因為在二進(jìn)制下對應(yīng)權(quán)值最低的八位代表列號，更高位代表行號，各部分都是能各自消掉的。
#include<bits/stdc++.h>
using namespace std;
#define N 300
int T,n,m,a[N][N];
int main()
{
for(int i=0;i<256*256;i++){
int x=i/256,y=i%256;
a[x][y]=i;
}
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
printf("%d\n",n*m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
printf("%d%c",a[i][j],j<m-1?' ':'\n');
}
}
1801B - Buying gifts
題目大意：有 \(n\) 個物品，每個物品有兩個權(quán)值 \(a_i,b_i\)分別表示該物品給 \(A,B\) 兩個人的權(quán)值。要求把這 \(n\) 個物品分配給兩人使得 \(|maxA-maxB|\) 盡可能小。\(maxA,maxB\) 分別表示兩人分配到物品的最大權(quán)值，每人至少要被分配一個物品。
這題我 FST 了，原因是當(dāng)所有物品一樣的時候我全買給了 \(A\)，好似！
這種題的做法有一個慣用套路就是固定其中一維然后求解。假設(shè)我們欽定了 \(maxA\) 的值，那么可以發(fā)現(xiàn)所有 \(a_i>maxA\) 的物品都必須給 \(B\)，而這時其它物品怎么選都不會影響 \(maxA\) 的值，那么在這些物品中選一個 \(b_i\) 與 \(maxA\) 最接近的給 \(B\) 即可。
于是就得到了一種做法，先把物品按照 \(a_i\) 排序，從小到大枚舉欽定哪一個物品是必須給 \(A\) 的，這時后面的所有物品就都得給 \(B\)，可以預(yù)處理后綴 \(\max\) 求出這一部分對 \(maxB\) 的貢獻(xiàn)。而對于前面選離 \(maxA\) 最近的值，利用 \(\mathrm{multiset}\) 中的 \(\mathrm{lower\_bound}\) 亂搞即可。
注意由于 \(a_i\) 的值可能相同，所以需要對相同的 \(a_i\) 分批處理，具體實現(xiàn)見代碼。
\(\mathrm{Find}\) 函數(shù)中的 \(o\) 就是特判之前 FST 的情況用的。
#include<bits/stdc++.h>
using namespace std;
#define N 500010
int n,f[N],ans;
multiset<int>s;
struct rua
{
int x,y;
void read(){scanf("%d%d",&x,&y);}
bool operator <(const rua &t)const{return x<t.x;}
}a[N];
int Find(int x,int y,int o)
{
int res=o?1e9:abs(x-y);
auto it=s.lower_bound(x);
if(it!=s.end()){
int z=max(y,*it);
res=min(res,abs(x-z));
}
if(it!=s.begin()){
it--;
int z=max(y,*it);
res=min(res,abs(x-z));
}
return res;
}
void init()
{
ans=2e9;
s.clear();
scanf("%d",&n);
for(int i=1;i<=n;i++)a[i].read();
sort(a+1,a+n+1);
f[n+1]=0;
for(int i=n;i>=1;i--)f[i]=max(a[i].y,f[i+1]);
for(int i=1,j;i<=n;i=j+1){
j=i;
while(j<=n && a[j].x==a[i].x)j++;j--;
int x=a[i].x;
int y=f[j+1];
for(int k=i;k<=j;k++)s.insert(a[k].y);
for(int k=i;k<=j;k++){
s.erase(s.find(a[k].y));
ans=min(ans,Find(x,y,j==n));
s.insert(a[k].y);
}
}
printf("%d\n",ans);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)init();
}
1801C - Music Festival
題目大意：定義一個序列 \(A\) 的價值為滿足 \(A_i=\max_{j=1}^{i}A_j\) 的 \(i\) 的個數(shù)。給定 \(n\) 個序列，要求以任意方式將他們拼接起來，使得得到的序列價值最大。
首先可以得到，對于每個序列，只有滿足對應(yīng)性質(zhì)的那些元素才有可能對答案產(chǎn)生貢獻(xiàn)，所以首先可以在輸入的時候就對序列進(jìn)行預(yù)處理，留下一個嚴(yán)格遞增的序列。
考慮 \(\mathrm{DP}\)，令 \(f_i\) 表示以數(shù)字 \(i\) 為結(jié)尾的序列的最大價值，那么可以得到如果把某個序列 \(A\) 接在尾部，對應(yīng)的方案只能更新到 \(f_{maxA}\) 上。于是考慮把序列按照最后一個元素大小進(jìn)行排序。
在 \(\mathrm{DP}\) 的過程中，考慮對每個序列枚舉該序列是從第幾個位置開始產(chǎn)生貢獻(xiàn)的。假設(shè)當(dāng)前在序列 \(A\) 中枚舉到的位置為 \(i\)（這題本人實現(xiàn)下標(biāo)是從 \(0\) 開始），序列處理后的長度為 \(k\)，最大值為 \(m\)，那么找到最大的 \(j\) 使得 \(j<a_i\) 且 \(f_j\) 有值，此時 \(f_j\) 就會對 \(f_m\) 產(chǎn)生 \(f_j+k-i\) 的貢獻(xiàn)，實時更新答案即可。\(j\) 的查找可以通過記錄所有當(dāng)前 \(f\) 有值的位置，\(\mathrm{lower\_bound}\) 一下即可。最后不要忘了多測清空。
#include<bits/stdc++.h>
using namespace std;
#define N 200010
int T,n,f[N];
struct rua
{
int m,k;
vector<int>d;
void init(){m=k=0;d.clear();}
void read(){
d.clear();
scanf("%d",&k);
for(int i=1;i<=k;i++){
int x;
scanf("%d",&x);
if(x<=m)continue;
d.push_back(x);
m=x;
}
k=d.size();
}
bool operator <(const rua &t)const{return m<t.m;}
}a[N];
vector<int>v;
void init()
{
int ans=0;
v.clear();
scanf("%d",&n);
for(int i=1;i<=n;i++){
a[i].init();
a[i].read();
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
for(int j=0;j<a[i].k;j++){
int x=a[i].d[j];
int k=lower_bound(v.begin(),v.end(),x)-v.begin()-1;
f[a[i].m]=max(f[a[i].m],a[i].k-j);
if(k>=0)f[a[i].m]=max(f[a[i].m],f[v[k]]+a[i].k-j);
ans=max(ans,f[a[i].m]);
}
v.push_back(a[i].m);
}
for(auto i:v)f[i]=0;
printf("%d\n",ans);
}
int main()
{
scanf("%d",&T);
while(T--)init();
}
1801D - The way home
題目大意：一個 \(n\) 個點 \(m\) 條邊的有向圖，每條邊有對應(yīng)花費。某個憨憨演唱家現(xiàn)在身上只有 \(p\) 元錢，他可以選擇在某個點 \(i\) 開演唱會以得到 \(s_i\) 的收入。問要從 \(1\) 走到 \(n\) 所需要舉辦的演唱會次數(shù)最小是多少。
首先考慮如果回家的路徑確定了，唱歌的決策是怎樣的。可以發(fā)現(xiàn)最后肯定是在某個點 \(x\) 死命唱歌直到恰好攢夠回家的錢，然后直接走最小花費的路徑跑路。接著再倒著往回推，在這之前他肯定也是在另一個點恰好攢夠錢后再動身來到 \(x\)。所以可以得到如果已經(jīng)選定了先后在哪些位置開演唱會，那么其唱歌決策是確定的，即每次在當(dāng)前位置一直舉辦演唱會直到攢夠前往下一個位置的錢。
于是跑 \(n\) 遍單源最短路，對所有 \((i,j)\) 預(yù)處理出從點 \(i\) 走到點 \(j\) 的最小花費 \(dis_{i,j}\)。再使用類似最短路的過程貪心選取下個演唱會的地點。那么在這一部分的最短路中，有兩個參考值，一個是 \(cost_i\) 表示到達(dá) \(i\) 這個點需要舉辦演唱會的最小次數(shù)，另一個是 \(res_i\) 表示在次數(shù)最小的前提下，所剩余錢數(shù)的最大值。那么根據(jù)這兩個信息跑最短路即可，每次到點 \(x\) 時，枚舉下一個唱歌的位置 \(i\)，根據(jù)當(dāng)前的 \(res_x\) 和 \(dis_{x,i}\) 的差值以及在 \(x\) 舉辦演唱會的收入 \(s_x\) 可以得到需要舉辦演唱會的次數(shù) \(k\)，直接轉(zhuǎn)移即可。最后答案就是 \(cost_n\)。
#include<bits/stdc++.h>
using namespace std;
#define N 810
#define LL long long
int T,n,m,p,b[N],vis[N];
LL dis[N],cost[N],res[N];
vector<pair<int,int>>d[N];
struct rua
{
int x;
LL cost,res;
bool operator <(const rua &t)const{
if(cost!=t.cost)return cost<t.cost;
return res>t.res;
}
};
set<rua>s;
void Dij(int x)
{
set<pair<LL,int>>q;
for(int i=0;i<=n;i++)dis[i]=1e18;
dis[x]=0;
for(int i=1;i<=n;i++)q.insert(make_pair(dis[i],i));
while(!q.empty()){
auto PI=*q.begin();
q.erase(q.begin());
int x=PI.second;
for(auto pi:d[x]){
LL nd=dis[x]+pi.second;
int y=pi.first;
if(nd<dis[y]){
q.erase(make_pair(dis[y],y));
dis[y]=nd;
q.insert(make_pair(dis[y],y));
}
}
}
}
LL ceil(LL x,LL y)
{
if(x<0)return 0;
if(x%y==0)return x/y;
return x/y+1;
}
void init()
{
s.clear();
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=n;i++){
d[i].clear();
scanf("%d",&b[i]);
vis[i]=0;
cost[i]=1e18;
res[i]=0;
}
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
d[u].push_back(make_pair(v,w));
}
Dij(1);
if(dis[n]==dis[0]){
printf("-1\n");
return;
}
cost[1]=0,res[1]=p;
s.insert((rua){1,cost[1],res[1]});
while(!s.empty()){
auto X=*s.begin();
s.erase(s.begin());
int x=X.x;
vis[x]=1;
Dij(x);
for(int i=1;i<=n;i++)if(!vis[i]){
LL k=ceil(dis[i]-res[x],b[x]);
rua tmp={i,cost[x]+k,res[x]+k*b[x]-dis[i]};
rua I={i,cost[i],res[i]};
if(tmp<I){
s.erase(I);
cost[i]=tmp.cost;
res[i]=tmp.res;
s.insert(tmp);
}
}
}
printf("%lld\n",cost[n]);
}
int main()
{
scanf("%d",&T);
while(T--)init();
}
賽場上為了省空間寫了個類似于最短路套最短路的玩意orz
1801E - Gasoline prices
不會捏，留坑待填
1801F - Another n-dimensional chocolate bar
題目大意：給定一個長度為 \(n\) 的數(shù)組 \(a\) 和正整數(shù) \(k\)，要求構(gòu)造一個數(shù)組 \(b\) 滿足 \(1\le b_i \le a_i\) 且 \(\prod_{i=1}^{n}b_i \ge k\)，使得 \(\lfloor \frac{a_1}{b_1} \rfloor \dotsm \lfloor \frac{a_n}{b_n} \rfloor \cdot \frac{1}{a_1 a_2 \cdots a_n} \cdot k\) 盡可能大，輸出這個最大值。
由于 \(a_i\) 和 \(k\) 已經(jīng)給出，所以就相當(dāng)于要在滿足條件的前提下最大化 \(\prod_{i=1}^{n}\lfloor \frac{a_i}{b_i} \rfloor\)。考慮一個樸素的 \(\mathrm{DP}\)，\(f_{i,j}\) 表示當(dāng)前到第 \(i\) 個位置，對應(yīng) \(b_i\) 的前綴乘積為 \(j\) 時，\(\lfloor \frac{a_i}{b_i} \rfloor\) 乘積的最大值。這樣直接做復(fù)雜度爆炸。
接著考慮優(yōu)化，因為要求的是 \(\prod b_i\ge k\)，所以不妨把 \(\mathrm{DP}\) 改成令 \(f_{i,j}\) 表示到第 \(i\) 個位置，要求剩下 \(b_i\) 乘積 \(>j\) 的答案，這樣轉(zhuǎn)移的時候 \(j\) 的值大概就能減少的很快，每次枚舉 \(b_i\) 的值就能直接從 \(j\) 轉(zhuǎn)移到 \(\lfloor\frac{j}{b_i}\rfloor\) 上。從 \(f_{1,k-1}\) 一路轉(zhuǎn)移到 \(f_{n,0}\) 就是答案。
這時發(fā)現(xiàn)在轉(zhuǎn)移過程中，實際上所有的 \(j\) 必然等于 \(\lfloor\frac{k-1}{x}\rfloor\)（\(x\) 為某個正整數(shù)），于是考慮數(shù)論分塊預(yù)處理出所有可能的 \(j\)，在這些位置間轉(zhuǎn)移即可，顯然這樣的 \(j\) 只有 \(O(\sqrt k)\) 個。而每次 \(i,j\) 能轉(zhuǎn)移到的位置數(shù)則是 \(O(\sqrt j)\) 個的，所以直接轉(zhuǎn)移的總復(fù)雜度與杜教篩類似，為 \(O(n\cdot k^{\frac{3}{4}})\)。
#include<bits/stdc++.h>
using namespace std;
#define N 110
#define ld long double
int n,m,k,x,a[N],b[N*N],id[1<<24];
ld f[N][N*N],ans=1;
int Fl(int x,int y){return x/y;}
int main()
{
scanf("%d%d",&m,&k);
ans*=k,k--;int kk=k;
for(int i=1;i<=m;i++){
scanf("%d",&x);
if(x>1)a[++n]=x;
ans/=x;
kk/=x;
}
if(kk)return printf("0\n"),0;
m=0;
for(int l=1,r;l<=k;l=r+1){
r=k/(k/l);
b[++m]=r;
id[r]=m;
}
f[0][m]=1;
for(int i=1;i<=n;i++){
f[i][0]=f[i-1][0]*a[i];
for(int j=1;j<=m;j++)if(f[i-1][j]){
x=b[j];
for(int l=1,r;l<=a[i];l=r+1){
int nxt=x/l;
if(nxt)r=x/nxt;else r=a[i];
f[i][id[nxt]]=max(f[i][id[nxt]],f[i-1][j]*Fl(a[i],l));
}
}
}
printf("%.10Lf\n",f[n][0]*ans);
}
浙公網(wǎng)安備 33010602011771號