D - Unique Username
题意:给出n个字符串,以任意顺序排列,然后在每两个字符串中间加最少一个"_",然后给出m个字符串,问是否能得出一个字符串,不在这m个字符串中,并且长度在3-16
题解: dfs即可
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; const int N=2e5+5; const ll inf=1e18; const ll mod=998244353; string s[N],p[N]; ll vis[N]; ll n,m; map<string,int> mp; void bfs(ll l,ll d,string st){ if(l==n+1){//如果最后一个字符串也加上了 if(!mp[st]&&st.size()>=3&&st.size()<=16){ cout<<st;exit(0); } } string beg=st; for(ll i=1;i<=n;i++){准备加上第几个字符串 for(ll j=1;d-j>=n-l-1;j++){//加几个"_",最多n-l-1,因为要保证后面得字符串都要有"_" if(!vis[i]){ vis[i]=1; st+=s[i]; if(l!=n){ ll pj=j; while(pj--) st+="_"; } bfs(l+1,d-j,st); vis[i]=0; st=beg; } } } } signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n>>m; ll sum=0; for(ll i=1;i<=n;i++){ cin>>s[i];sum+=s[i].size(); } for(ll i=1;i<=m;i++){ string x;cin>>x; mp[x]=1; } if(sum+n-1>16){ cout<<"-1";return 0; } bfs(1,16-sum,"");//16-sum就是出去字符串的长度,可以最多添加几个"_" cout<<"-1"; }
E - Chinese Restaurant (Three-Star Version)
题意: n个人,每个人开始有一个值,然后可以将值逆时针旋转,设k为某个值,第i个人的k为(i+k)%n=a[i]或者(i-k+n)%n=a[i],问k的总和的最小值
题解: 对于每个人,数值逆时针旋转,他们的每个位置的最小值都是以一种可知的函数方式变化
类似这种,所以我们可以利用差分写出每个位置的函数的参数,从而求出每个位置的值进行比较。
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; const int N=2e5+5; const ll inf=1e18; const ll mod=998244353; ll th[N],a[N]; ll sum[N]; ll p[N],q[N],n; void add(ll l,ll r,ll x,ll y){// y=ax+b 四个参数分别是这段函数的起点和终点,a,b if(l<=r){ p[l]+=x; q[l]+=y; p[r+1]-=x; q[r+1]-=y; } } void solve (ll x){//函数的自变量就是旋转次数 if(x<n/2){ add(0,x-1,-1,x);//0 - x-1距离逐渐变小 add(x,x+n/2,1,-x); add(x+n/2+1,n-1,-1,n+x); } else{ add(0,x-n/2-1,1,n-x); add(x-n/2,x,-1,x); add(x+1,n-1,1,-x); } } signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>n; for(ll i=0;i<n;i++) cin>>a[i]; for(ll i=0;i<n;i++){ ll pt=(a[i]-i+n)%n; solve(pt); } for(ll i=1;i<n;i++){//差分 p[i]+=p[i-1];q[i]+=q[i-1]; } ll ans=inf; for(ll i=0;i<n;i++){//i表示的是逆时针旋转的次数,最多n-1次 ans=min(ans,p[i]*i+q[i]); } cout<<ans; }
标签:AtCoder,typedef,const,Beginner,ll,st,字符串,268,sum From: https://www.cnblogs.com/hhzp/p/16726257.html