水博客
反省为什么练了这么久还这么拉
可能真是sb
zhihu偷图
round#826
D:
题意：一颗二叉树的所有最小儿子上分布着1-n的不同数，问时候可以交换任意个结点的左右儿子，使得最后最小儿子从左到右递增排序，输出ans值
dfs跑一下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| int a[N],ans=0;
void dfs(int l,int r){
if(l>=r)return ;
if(l+1==r){
if(a[l]>a[r]){
swap(a[l],a[r]);
ans++;
}else return ;
}
dfs(l,(l+r)/2);
dfs((l+r)/2+1,r);
if(a[l]>a[(l+r)/2+1]){
ans++;
int k=(r-l)/2+1;
rep(i,l,(l+r)/2){
swap(a[i],a[i+k]);
}
}
}
void solve()
{
int n;cin>>n;
ans=0;
rep(i,1,n)cin>>a[i];
dfs(1,n);
rep(i,1,n)
if(a[i]<a[i-1]){
cout<<-1<<endl;
return ;
}
cout<<ans<<endl;
}
|
F ：
题意：给定一个数组，问是否可以将其分为若干连续段，使得每一段的最左或最右值表示该段中其他元素的个数
左右dp一下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| const int N=3e5+10;
int dp[N],a[N];
void solve()
{
int n;cin>>n;
rep(i,1,n)cin>>a[i];
memset(dp,0,sizeof dp);
dp[0]=1;
rep(i,1,n){
if(i>=a[i]+1)dp[i]|=dp[i-a[i]-1];
if(a[i]+i<=n)dp[a[i]+i]|=dp[i-1];
}
if(dp[n])cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
|
round#827
这道题卡了好久。。。
D:一个数组是否使得其中gcd(a[i],a[j])==1，求i+j的最大值
因为a[i]<=1000，所以map存一下暴力，我他妈脑子有坑,还用暴力tle了两发
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| map<int,int>p;
void solve()
{
int n,ans=-1;cin>>n;
p.clear();
rep(i,1,n){
int x;cin>>x;
p[x]=i;
}
for(auto [x,y]:p){
for(auto [xx,yy]:p){
if(__gcd(xx,x)==1){
ans=max(ans,y+yy);
}
}
}
cout<<ans<<endl;
}
|
E：前缀和，前最大值存一下二分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| ll a[N],p[N],h[N];
void solve()
{
ll n,m;cin>>n>>m;
rep(i,1,n){
cin>>a[i];
p[i]=max(a[i],p[i-1]);
h[i]=h[i-1]+a[i];
}
while(m--){
ll x;cin>>x;
ll l=1,r=n;
while(l<=r){
int k=(l+r)>>1;
if(x>=p[k])l=k+1;
else r=k-1;
}
cout<<h[r]<<' ';
}
cout<<endl;
}
|
F:问每次操作给初始字符串都为’a’的s和t加k次字符串x，是否可以排序使得a<b
记录操作后a和b的最大字符和长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void solve() {
int n,lens=1,lent=1;cin>>n;
char maxs='a',maxt='a';
rep(i,1,n){
int o,k;string s;cin>>o>>k>>s;
for(auto c:s){
if(o==1) {
maxs=max(maxs,c);
lens+=k;
} else {
maxt=max(maxt,c);
lent+=k;
}
}
if('a'<maxt||('a'==maxt&&'a'==maxs&&lens<lent))cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
|
G:重新排列数组a，使得a的前缀异或和按最大排列
int二进制位只有三十多，所以排列前31次找出按位补1位的最大值，剩下的随便
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| int a[N],num;
bool cmp(int a,int b){
return (a|num) > (b|num);
}
void solve()
{
int n;cin>>n;
num=0;
rep(i,1,n)cin>>a[i];
rep(i,1,min(31,n)){
sort(a+i,a+n+1,cmp);
num|=a[i];
}
rep(i,1,n)cout<<a[i]<<' ';
cout<<endl;
}
|
起床想到的第一件事就是我怎么这么废，这都没ak，二十几号还有两门结课考试，忙去了。。。
