模拟赛
咕了两天才发现少了一天的题解。
T1 Make It Increasing
水。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 40;
#define LL long long
int t,n;
LL a[N];
int main()
{
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
scanf("%d",&t);
while(t--)
{
LL ans=0; bool fl=0;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=n-1;i>=1;i--)
{
while(a[i]>=a[i+1])
{
if(!a[i+1])
{
fl=1; break;
}
a[i]>>=1; ans++;
}
if(fl) break;
}
if(fl) printf("-1\n");
else printf("%lld\n",ans);
}
return 0;
}
T2 Shrinking
二分，水，注意判等。
其实是道线性的，但不会有人卡 log 吧。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
int n;
char s[N];
int a[26][N],cnt[26];
bool check(int mid)
{
for(int i=0;i<26;i++)
{
for(int j=1;j<=cnt[i];j++)
{
if(a[i][j]-a[i][j-1]-1>mid) break;
if(a[i][j]>=n-mid) return 1;
}
}
return 0;
}
int main()
{
//freopen("string2.in","r",stdin);
scanf("%s",(s+1)); n=strlen(s+1);
for(int i=1;i<=n;i++) a[s[i]-'a'][++cnt[s[i]-'a']]=i;
int l=0,r=n,ans=n-1;
while(l<=r)
{
int mid=l+r>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d\n",ans);
return 0;
}
T3 Game on Tree
学习博弈论。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n;
vector<int> v[N];
int dfs(int u,int f)
{
int res=0;
for(int i:v[u]) if(i!=f) res^=dfs(i,u)+1;
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1,x,y;i<n;i++)
{
scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
puts(dfs(1,0)?"Alice":"Bob");
return 0;
}