比賽經過：寫了七八題，有一個topsort寫錯地方了，本場題目都較為簡單考的知識都比較明顯
補題：有些題目還得多思考其實也不難
目錄
B.阿強的路
C.傳染病統計
D.阿強與網格
E.生活大爆炸
F.Capslock
G.字節類型
H.制造游戲幣
I.完美主義
L.神奇的回答
M.比賽!
B.阿強的路
floyd變式
考慮到數據范圍圖論知識可以聯想到floyed,注意題目要的結果是兩點之間路徑中的最大點權*最大邊權最小，我們對于路徑a-b就是要找到用了哪些點，跑了哪些邊，由于floyd的性質本質就是dp，在用前k個點的時候的最短路，我們不妨按照點權排序去跑第k層,對于當前層次如果邊權比我的大，說明在之前有一個邊權更小的同時點權最小的答案當前不需要更新答案,本題重復考察了floyd的性質理解
int w[M];
LL g[M][M],f[M][M]; // 兩邊之間的最短路的最大邊權和 兩點之間最短路的最大邊權*最大點權
struct code{int w,id;bool operator<(const code&t)const{return w<t.w;}
}e[N];void solve(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>w[i];e[i]={w[i],i};}sort(e+1,e+1+n);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)f[i][j]=g[i][j]=2e18;while(m--){int a,b;LL c; cin>>a>>b>>c;g[a][b]=g[b][a]=min(g[a][b],c);f[a][b]=f[b][a]=min(f[a][b],g[a][b]*max(w[a],w[b]));}for(int k=1;k<=n;k++)// 按照點權來排序使用最大的邊權for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(g[i][j]>max(g[i][e[k].id],g[e[k].id][j])){ // 當前的大于 [i,e[k].id] 和 [e[k].id,j]g[i][j] = max(g[i][e[k].id],g[e[k].id][j]);f[i][j] = min(f[i][j],g[i][j]*max({w[i],w[j],e[k].w}));}// 由于我們是按照點權去跑的k如果當前的百年大于i,j的話說明前面有更小的點和更小的邊權for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j) f[i][j]=0;if(f[i][j]>1e18) f[i][j]=-1;cout << f[i][j] << ' ';}cout << endl;}return ;
}C.傳染病統計
暴力
看起來我們需要思考一下性質考慮并查集啥的但是注意到數據范圍,我們直接排序之后對于每一個數一直左右跑即可
int a[15];void solve(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+1+n);int smax = 0, smin = n;for(int i=1;i<=n;i++){int j= i+1;int cnt = 1;while(j<=n and a[j]-a[j-1]<=2){cnt++;j++;}j=i-1;while(j>=1 and a[j+1]-a[j]<=2){cnt++;j--;}smax=max(smax,cnt);smin=min(smin,cnt);}cout << smin << ' ' << smax << endl;return ;
}D.阿強與網格
數學小推理
對于數據范圍我們可以發現肯定是要推出一些小式子的在o(1)的時間復雜度解決這個問題
對于特例可以直接判斷，重合的，只有一條線的，我們可以作圖模擬一下，當我的點沒有抵達n,m同行或者同列的時候從可以直接跳min(n,m)-1到同一層,接著發現如果(n+m）是偶數的話是可以直接跳過去的否則就是必須走一步,對于到了同一層之后我們發現后面的跳和走步數是一樣的就是做差，最優解就是 1.一直走過去 2.一直跳過去 3.跳過去之后走
int t,n,m,x,y;void solve(){cin>>n>>m>>x>>y;if(n==1 and m==1){ // 重合的點直接輸出答案cout << 0 << endl;return ;}LL res1 = (LL)(n-1+m-1)*x; // 直接一步一步if(n==1 or m==1){ // 無法跳躍cout << res1 << endl;return ;}int ok = (n+m)%2;if(m>n) swap(n,m);int X = 1 + m-1 ,Y = m;LL res2 = (LL)(m-1)*y;LL cnt = n - X; // 步數if(cnt==0){ // 直接跳到了cout << min(res1,res2) << endl;return ;}if(ok){// 奇數 需要走一步res2 += min((LL)(cnt-1)*y+x,(LL)cnt*x);cout << min(res1,res2) << endl;}else{res2 += min((LL)cnt*y,(LL)cnt*x);cout << min(res1,res2) << endl;}return ;
}E.生活大爆炸
小組合數公式
直接使用小范圍組合數公式暴力求解即可
LL C[M][M];void init(){for(int i=0;i<M;i++)for(int j=0;j<=i;j++)if(!j) C[i][j]=1;else C[i][j]=C[i-1][j]+C[i-1][j-1];
}
void solve(){cin>>n>>m>>t;LL ans = 0;for(int i=4;i<=n;i++)for(int j=1;j<=m;j++){if(i+j==t){ans += (LL)C[n][i]*C[m][j];}}cout << ans << endl;return ;
}F.Capslock
簡單小模擬
使用islower(),toupper(),tolower()函數
void solve(){string s; cin>>s;n = s.size(); s=' '+s;int ok1 = islower(s[1]),cnt = 0;for(int i=1;i<=n;i++){if(isupper(s[i])) cnt++;}if(cnt==n){for(int i=1;i<=n;i++) s[i]=tolower(s[i]);}else if(ok1 and cnt==n-1){s[1] = toupper(s[1]);for(int i=2;i<=n;i++) s[i] = tolower(s[i]);}for(int i=1;i<=n;i++) cout << s[i];cout << endl;return ;
}G.字節類型
大數比較
比較兩個大數，直接先數位后大小即可
string s[N]={"127","32767","2147483647","9223372036854775807"," "};
string ans[N]={"byte","short","int","long","BigInteger"};void solve(){auto check = [&](string&a,string&b){if(a.size()>b.size() or a==b) return true;if(a.size()<b.size()) return false;n = a.size();for(int i=0;i<n;i++){if(a[i]==b[i]) continue;return a[i]>b[i];}return true;};string a; cin>>a;for(int i=0;i<=4;i++){if(i==4 or check(s[i],a)){cout << ans[i] << endl;return ;}}return ;
}H.制造游戲幣
有限制性的背包
可以發現要求有a的數量一定是大于b，說明，在買a的時候一定是要買b的有一個綁定的性質
我們可以建圖來確定綁定關系，明顯的如果說有環的話一定是無解的，他那個是注意到對于這個綁定性質可以使用dfs去跑，變成選這個物品要有的真實連帶花費
int dp[N],p[N];
LL w[N];
bool in[N];
vector<int> g[N];
int find(int x){if(x!=p[x]) p[x]=find(p[x]);return p[x];
}
void dfs(int u){for(auto&v:g[u]){w[v] += w[u];dfs(v);}if(!g[u].empty()) T -= w[u];// 表示嚴格的大于關系
}
void solve(){cin>>n>>m>>T;for(int i=1;i<=n;i++) cin>>w[i],p[i]=i;bool ok = false;while(m--){int a,b; cin>>a>>b;in[b]=true;g[a].push_back(b);int fa = find(a), fb = find(b);if(fa==fb){ok = true;}else{p[fa]=fb;}}if(ok){// 表示矛盾了cout << 0 << endl;return ;}for(int i=1;i<=n;i++) if(!in[i]) dfs(i);dp[0] = 1;for(int i=1;i<=n;i++)for(int j=w[i];j<=T;j++){dp[j] += dp[j-w[i]];dp[j] %= mod;}cout << dp[T] << endl;return ;
}I.完美主義
線段樹
明顯的直接使用線段樹維護即可，bool表示當前區間是否可行,同時維護每個區間的左右端點數用于兩個區間結合的時候的判斷
int w[N];
struct code{int l,r;int lx,rx;bool ok;
}tr[4*N];void pushup(code&u,code&l,code&r){if(!l.ok or !r.ok) u.ok = false;else{if(l.rx<=r.lx){u.ok = true;}else{u.ok = false;}}u.lx = l.lx,u.rx = r.rx;
}void pushup(int u){pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}void build(int u,int l,int r){if(l==r){tr[u]={l,r,w[l],w[l],1};return ;}tr[u]={l,r};int mid=l+r>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);pushup(u);
}void modify(int u,int v ,int x){if(tr[u].l== v && v==tr[u].r){tr[u].lx = x ;tr[u].rx = x;return ;}int mid=tr[u].l+tr[u].r>>1;if(v<=mid) modify(u<<1,v,x);if(v>mid) modify(u<<1|1,v,x);pushup(u);
}code query(int u,int l,int r){if(tr[u].l>=l && tr[u].r<=r){return tr[u];}int mid=tr[u].l+tr[u].r>>1;if(r<=mid) return query(u<<1,l,r);else if(l>mid) return query(u<<1|1,l,r);else{code res;code ll=query(u<<1,l,r);code rr=query(u<<1|1,l,r);pushup(res,ll,rr);return res;}
}
void solve(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>w[i];build(1,1,n);while(m--){int op,l,r; cin>>op>>l>>r;if(op==1){modify(1,l,r);}else{code t = query(1,l,r);cout << (t.ok ? "Yes" : "No") << endl;}}return ;
}L.神奇的回答
簡單模擬
void solve(){int x; cin>>x;if(x<18) cout << x << endl;else cout << 18 << endl;return ;
}M.比賽!
topsort
按照題目映射一下直接跑topsort即可
int idx;
vector<int> g[N];
int in[N];
int q[N];
bool use[M][M];
void solve(){cin>>n;while(n--){char a,op,b,c;cin>>a>>op>>b>>c;if(!mp.count(a)){mp[a]=++idx;G[idx]=a;}if(!mp.count(b)){mp[b]=++idx;G[idx]=b;}if(!mp.count(c)){mp[c]=++idx;G[idx]=c;}int A = mp[a], B = mp[b] , C = mp[c];in[A]++,in[C]++;g[B].push_back(A);g[A].push_back(C); }vector<int> ans;auto topsort = [&](){queue<int> q;for(int i=1;i<=idx;i++) if(!in[i]) q.push(i);while(!q.empty()){int u = q.front(); q.pop();ans.push_back(u);for(auto&v:g[u]){if(--in[v]==0) q.push(v);}}return (int)ans.size() == idx;};if(topsort()){for(auto&v:ans) cout << G[v];cout << endl;}else{cout << "No Answer" << endl;} return ;
}
算法總結)
