6.15训练日记

日记"/>

6.15训练日记

烦心事很多,但打代码一定要心静不能焦躁。平静平静.
惯例,先打卡cf先。

D. Required Length

链接
思路:naive地想,一开始找一个最大的数字嗯乘上去,比如说有一个9,就一直乘9,可能是最优的.但考虑到不是每次都有9,可能需要一些路径先生成一些更大的单个数字.然后考虑到每次都是x*个位数.
那么这个个位数做唯一分解
d i g i t = 2 a ∗ 3 b ∗ 5 c ∗ 7 d digit=2^a*3^b*5^c*7^d digit=2a∗3b∗5c∗7d
可以发现,可能的组合并不多,考虑直接bfs去暴力它.

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);ll n,x;cin>>n>>x;map<ll,int> dis;dis[x] = 0;queue<ll> q;q.push(x);int ans = -1;while(!q.empty()){ll y = q.front();q.pop();string str = to_string(y);if(str.length()==n){ans = dis[y];break; }for(auto ch : str){if(ch=='0') continue;ll nxt = (int)(ch-'0')*y;if(!dis.count(nxt)){dis[nxt] = dis[y] +1;q.push(nxt);}}}cout<<ans<<"\n";
}

和某人吵了一架,心情不快,但又无处可泄,遂摆烂.
过三时,幡然醒悟,继续训练.

二:C. Binary String

链接
还是手不太熟,调了比较多的时间.一个比较常见的区间问题和位置经典问题,没有很好地联想到之前学过的一些题目.

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
int n,m;
int S[maxn];vector<int> pos;
bool check(int k){if(k>=m) return true;for(int i=k;i>=0;i--){if(k==0){if(S[pos[m-1]]-S[pos[0]]<=0) return true;}else if(i==k){int l = pos[k];int num = S[pos[m-1]] - S[l];if(num<=k) return true;}else{int l = pos[i];int r = pos[m+i-k-1];int num = S[r] - S[l];if(num<=k) return true;}}return false;
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin>>T;while(T--){string s;cin>>s;n = s.length();pos.clear();for(int i=0;i<n;i++){S[i+1] = S[i] + (s[i]=='0');if(s[i]=='1') pos.push_back(i+1);}m = pos.size();int L = 0,R = m;int ans = m;while(L<=R){int mid = L+R>>1;if(check(mid)) ans=mid,R = mid-1;else L = mid+1;}check(1);cout<<ans<<"\n";}
}

三:E. Advertising Agency

链接
简单的组合,发现需要贪心地选取前k个大,剩余的可用的和最后剩下的组合数一下就是答案.

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll mod = 1e9+7;
ll fac[maxn];
ll f_pow(ll a,ll b){a%=mod;ll ans =1;while(b){if(b&1) ans = ans*a%mod;a=a*a%mod;b>>=1;}return ans%mod;
}
ll inv(ll n) {return f_pow(n,mod-2)%mod;
}
ll C(ll n,ll m){return fac[n]*inv(fac[m])%mod*inv(fac[n-m])%mod;
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);fac[1]=fac[0]=1;for(int i=2;i<=1000;i++) fac[i] = fac[i-1]*i%mod;int T;cin>>T;while(T--){int n,k;cin>>n>>k;map<int,int> cntt;for(int i=1;i<=n;i++){int x;cin>>x;cntt[x]++;}vector<pii> vec;for(auto [x,y]:cntt){vec.push_back({x,y});}sort(vec.begin(),vec.end());reverse(vec.begin(),vec.end());ll ans = 1;for(auto [x,cnt]:vec){if(k>=cnt) k-=cnt;else {ans=(C(cnt,k)%mod);break;}}cout<<ans<<"\n";}
}

看了洛谷的一题Tarjan,没有想好,先玩会游戏吃个饭,休息好了回来继续写.
玩了一会刺客信条,育碧罐头果然吃不动,打开戴森球又觉得没有时间玩,看来以后休息还是玩玩手游看看书罢了.

五:嗅探器

链接
题意:给你一个无向图,有两个特殊的点 s , t s,t s,t.求点 u u u,使得去掉 u u u后,s与t不再连通.
思路:一开始理解题意倒是挺困难的.简化为上面的问题后,不难想到割点的定义.
根据割点的定义,如果去掉某个割点后,形成的两个新的连通分量分别包含了 s , t s,t s,t两点在两部分,就满足了定义.去掉割点后,大致形成了三个部分,第一个部分是和根节点连接的,第二个部分是u的子树系列,第三部分是形成割点边u->v的那个双连通分量和下边的子树.
如果我们从s开始跑Tarjan,那么s就是根在第一部分,如果t在第二部分,其实并不能保证它一定和s,t割掉u后不连通,这个部分需要对应的那个割点来判定,唯一可以知道的,如果t在第三部分,那么割掉u后,s,t就会不再连通.
说了这么多,就是在Tarjan找到割点的时候,再判一下有没有
d f n [ v ] < = d f n [ b ] dfn[v]<=dfn[b] dfn[v]<=dfn[b]

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
vector<int> G[maxn];
int dfn[maxn],low[maxn],dfs_clock=0;
bool is_cut[maxn];
int s,t;
void dfs(int u,int fa){low[u] = dfn[u] = ++dfs_clock;int child = 0;for(auto v :G[u]){if(!dfn[v]){child++;dfs(v,u);low[u] = min(low[u],low[v]);if(low[v]>=dfn[u]){if(dfn[t]>=dfn[v]) is_cut[u] = true;}}else if(dfn[v]<dfn[u]&&v!=fa){low[u] = min(low[u],dfn[v]);}}if(fa==0&&child==1) is_cut[u] = false;
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,uu,vv;cin>>n;while(cin>>uu>>vv){if(uu==0&&vv==0) break;G[uu].push_back(vv);G[vv].push_back(uu);}cin>>s>>t;dfs(s,0);int ans = -1;for(int i=1;i<=n;i++){if(is_cut[i]){if(i!=s&&i!=t){ans = i;break;}}}if(ans!=-1) cout<<ans<<"\n";else cout<<"No solution\n";
}

今天就这样结束了,心情还不是很好吧,但还是尽量不要让其他事干扰训练,16训练加油