前言
补题补题补题
一、A. Trippi Troppi
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
for(int i=0;i<3;i++)
{
string s;
cin>>s;
cout<<s[0];
}
cout<<endl;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)
{
solve();
}
return 0;
}签到题，每次输出第一个字符即可，没啥好说的。
二、B. Bobritto Bandito
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
int n,m,l,r;
cin>>n>>m>>l>>r;
for(int i=n;i>m;i--)
{
if(l<0)
{
l++;
}
else
{
r--;
}
}
cout<<l<<" "<<r<<endl;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)
{
solve();
}
return 0;
}因为给出一种可能性即可，所以只要从后往前推，左边界小于零就算左侧的，否则就算右边界的即可。
三、C. Brr Brrr Patapim
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
int n;
cin>>n;
vector<vector<int>>grid(n+1,vector<int>(n+1));
vector<bool>vis((n<<1)+1);//注意数字的范围是2n！！！
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>grid[i][j];
vis[grid[i][j]]=true;
}
}
for(int i=1;i<=(n<<1);i++)
{
if(!vis[i])
{
cout<<i<<" ";
break;
}
}
for(int j=1;j<=n;j++)
{
cout<<grid[1][j]<<" ";
}
for(int i=2;i<=n;i++)
{
cout<<grid[i][n]<<" ";
}
cout<<endl;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)
{
solve();
}
return 0;
}观察可得整个矩阵是对角线对称的，所以先统计出第0号数，再沿着边界摸一遍即可。
四、D. Tung Tung Sahur
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string p,s;
int n,m;
//TLE错解
bool dfs(int i,int j)
{
if(i>=n&&j<m)
{
return false;
}
if(i<n&&j>=m)
{
return false;
}
if(i==n&&j==m)
{
return true;
}
bool ans=false;
if(p[i]==s[j])
{
ans=ans||dfs(i+1,j+1);
if(p[i]==s[j+1])
{
ans=ans||dfs(i+1,j+2);
}
}
return ans;
}
bool ways1()
{
return dfs(0,0);
}
bool ways2()
{
if(n>2*m)
{
return false;
}
int j=0;
for(int i=0,cntp,cnts;i<n;i++,j++)
{
if(p[i]!=s[j])
{
return false;
}
if(j>=m)
{
return false;
}
cntp=1;
cnts=1;
while(i+1<n&&p[i]==p[i+1])
{
i++;
cntp++;
}
while(j+1<m&&s[j]==s[j+1])
{
j++;
cnts++;
}
if(cnts>2*cntp||cnts<cntp)
{
return false;
}
}
//边界讨论！！！！！！！！！！
if(j<m)
{
return false;
}
return true;
}
string randomString(int n)
{
string str;
for(int i=0,tmp;i<n;i++)
{
tmp=rand()%2;
str+=(tmp?"L":"R");
}
return str;
}
void solve()
{
cin>>p>>s;
n=p.length();
m=s.length();
//对数器
// srand(time(0));
// int testTime=10000;
// for(int i=0;i<testTime;i++)
// {
// int n=rand()%10000+1;
// int m=rand()%20000+1;
// p=randomString(n);
// s=randomString(m);
// bool ans1=ways1();
// bool ans2=ways2();
// if(ans1!=ans2)
// {
// cout<<"Wrong!"<<endl;
// cout<<p<<endl<<s<<endl;
// }
// }
// cout<<"Over"<<endl;
cout<<(ways2()?"YES":"NO")<<endl;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)
{
solve();
}
return 0;
}ways1就是双指针暴力递归，然后喜提TLE。
然后再观察两个字符串的特征，可以发现可以根据p串里听到的声音在s串中分组，那么对于任意一组，听到的声音必然全和敲击的位置相同，且听到的次数必然介于一倍敲击次数到两倍敲击次数之前。所以那就设两个指针，然后进行分组滑动即可。重点要注意这些边界讨论，因为这个爆了两次WA……
五、E. Boneca Ambalabu
#include <bits/stdc++.h>
using namespace std;
//每一位相互独立 -> 拆位计算，最后计算总贡献
typedef long long ll;
void solve()
{
int n;
cin>>n;
vector<int>nums(n);
vector<int>cnts(32,0);
for(int i=0;i<n;i++)
{
cin>>nums[i];
for(int j=0;j<32;j++)
{
cnts[j]+=((nums[i]>>j)&1);//统计这位上有几个1
}
}
ll ans=0;
for(int i=0;i<n;i++)
{
ll sum=0;
for(int j=0;j<32;j++)
{
int bit=(nums[i]>>j)&1;
//计算贡献
if(bit==0)
{
sum+=cnts[j]*((ll)1<<j);//开long long!!!
}
else
{
sum+=(n-cnts[j])*((ll)1<<j);//开long long!!!
}
}
ans=max(ans,sum);
}
cout<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)
{
solve();
}
return 0;
}这下真不开long long见祖宗了……
这个题就提供了一种新思路，对于位运算相关的题，若每位在计算贡献时相互独立，那么就可以考虑进行拆位，将所有数的同一位累加起来，最后计算总贡献。
具体实现就是用个cnts表存所有数在该位上1的数量，然后只需要遍历一遍枚举ak即可。对于每个ak，就是取ak每一位的数字，若是0，那就只有和1异或得到1才能对累加和产生贡献，所以就从cnts数组里拿个数，再乘以该位的权值。若是1那就找0的个数即可。
六、F. Trulimero Trulicina
#include <bits/stdc++.h>
using namespace std;
//注意：要求三是指上下左右的数都不相同
//思路：1.若m%k!=0，则从上往下从左往右顺着1~k填即可
// 横向必满足，纵向两数之间必差m个数，又因为m%k!=0，所以必不同
// 2.若m%k==0，就考虑每行分成m/k个区域，每个区域顺着填，下一行往前移一个填
// e.g.当m=9,k=3 -> 123 123 123
// 231 231 231
// 123 123 123
// ……
typedef long long ll;
int n,m,k;
void solve()
{
cin>>n>>m>>k;
vector<vector<int>>grid(n,vector<int>(m));
if(m%k!=0)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
grid[i][j]=(m*i+j)%k+1;
}
}
}
else
{
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
grid[i][j]=i%2==0?j%k+1:(j+1)%k+1;
}
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cout<<grid[i][j]<<" ";
}
cout<<endl;
}
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)
{
solve();
}
return 0;
}这个构造题的思路太逆天了……
注意到（注意力惊人），若m%k不等于0，那直接从上往下从左往右顺着填1～k即可。这样的话左右肯定不相同，而上下的话观察可得两数中间正好差k个数，又因为m%k不等于0，所以上下必不可能相等。若m%k等于0，那就考虑将列分成m/k个区域，第一行每个区域从1～k顺着填，第二行把1～k往前移一位，按照2，3，4～k，1这个顺序填，第三行再从1～k，之后轮换两种填法即可。（逆天思路）
七、G. Chimpanzini Bananini
#include <bits/stdc++.h>
using namespace std;
//纯纯数据结构设计题
//思路：同时维护正序和、逆序和，并用变量记录是否处于reverse状态
typedef long long ll;
typedef pair<int,int> pii;
void solve()
{
int q;
cin>>q;
deque<int>nums;
bool rev=false;//记录是否处于reverse状态
ll sum1=0;//正序累加和
ll sum2=0;//逆序累加和
ll sum=0;//数字累加和
ll head1=1;//正序的头下标 -> 初始值不影响最后结果，能修正回来
ll head2=1;//逆序的头下标
auto put=[&](bool dir,int k){
sum+=k;
if(!dir)//尾插
{
//e.g. k=6
//操作前：
// num: 5 1 2 3 4
// idx1: 0 1 2 3 4
// idx2: 4 3 2 1 0
// idx: 1 2 3 4 5
// nums.size()=5,head1=0,head2=0
//操作后：
// num: 5 1 2 3 4 6
// idx1: 0 1 2 3 4 5
// idx2: 4 3 2 1 0 -1
// idx: 1 2 3 4 5 6
// nums.size()=6,head1=0,head2=1,sum1+=(0+5)*6,sum2+=(-1)*6
sum1+=(head1+nums.size())*k;//
sum2+=(--head2)*k;
nums.push_back(k);
}
else
{
sum1+=(--head1)*k;
sum2+=(head2+nums.size())*k;
nums.push_front(k);
}
};
while(q--)
{
int op;
cin>>op;
if(op==1)///旋转
{
if(!rev)//正序
{
int x=nums.back();
nums.pop_back();
sum-=x;
//操作前：
// num: 1 2 3 4 5
// idx1: 1 2 3 4 5
// idx2: 5 4 3 2 1
// idx: 1 2 3 4 5
// nums.size()=5,head1=1,head2=1
//操作后：
// num: 1 2 3 4
// idx1: 1 2 3 4
// idx2: 5 4 3 2
// idx: 1 2 3 4
// nums.size()=4,head1=1,head2=2,sum1-=(1+4)*5,sum2-=1*5
sum1-=(head1+nums.size())*x;
sum2-=head2*x;
head2++;//逆序头左移
//操作前：
// num: 1 2 3 4
// idx1: 1 2 3 4
// idx2: 5 4 3 2
// idx: 1 2 3 4
// nums.size()=4,head1=1,head2=2
//操作后：
// num: 5 1 2 3 4
// idx1: 0 1 2 3 4
// idx2: 6 5 4 3 2
// idx: 1 2 3 4 5
// nums.size()=5,head1=0,head2=2,sum1+=0*5,sum2+=(2+4)*5
put(true,x);//头插
}
else
{
int x=nums.front();
nums.pop_front();
sum-=x;
//操作前：
// num: 1 2 3 4 5
// rev: 5 4 3 2 1
// idx1: 1 2 3 4 5
// idx2: 5 4 3 2 1
// idx: 1 2 3 4 5
// nums.size()=5,head1=1,head2=1
//操作后：
// num: 2 3 4 5
// rev: 5 4 3 2
// idx1: 2 3 4 5
// idx2: 4 3 2 1
// idx: 1 2 3 4
// nums.size()=4,head1=2;head2=1,sum1-=1*1,sum2-=(1+4)*1
sum2-=(head2+nums.size())*x;
sum1-=head1*x;
head1++;
//操作前：
// num: 2 3 4 5
// rev: 5 4 3 2
// idx1: 2 3 4 5
// idx2: 4 3 2 1
// idx: 1 2 3 4
// nums.size()=4,head1=2,head2=1
//操作后：
// num: 2 3 4 5 1
// rev: 1 5 4 3 2
// idx1: 2 3 4 5 6
// idx2: 4 3 2 1 0
// idx: 1 2 3 4 5
// nums.size()=5,head1=2;head2=0,sum1+=(2+4)*1,sum2+=0*1
put(false,x);//尾插
}
}
else if (op==2)//反转
{
rev=!rev;
}
else //添加
{
int k;
cin>>k;
put(rev,k);
}
//输出时，因为head会因为put小于，所以要加上1到head的距离修正
//e.g.队列数字： 6 1 2 3 4 5
// 维护下标： -1 0 1 2 3 4 head1=-1
// 实际下标： 1 2 3 4 5 6
// sum=1+2+3+4+5+6=21
// sum1=-6+0+2+6+12+20=34
// ans=6+2+6+12+20+30=76
// 所以ans=sum1+sum*(1-(head1))=34+21*2=76
if(!rev)
{
cout<<sum1+sum*(1-head1)<<endl;
}
else
{
cout<<sum2+sum*(1-head2)<<endl;
}
}
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)
{
solve();
}
return 0;
}这个题感觉已经不能用逆天来形容了……
因为必须实现每个操作的时间复杂度都为常数时间，所以就得考虑设计多个数据结构，用空间换时间。
观察可得，因为其中有反转操作，所以考虑同时维护正序指标sum1和逆序指标sum2，再用一个变量记录当前状态是否为反转，最后输出时直接根据状态输出对应指标即可。
接着就需要考虑将旋转和添加操作转化成只对sum1和sum2两头进行操作，而不对中间值操作，最后输出答案的时候再通过别的方法一步修正对。思路就是去修改正序和逆序的下标，若当前状态是正序，在旋转时就是先让sum1减去下标乘以最后一个数。而在头部插入这个数时，因为要尽可能减小对中间值的影响，所以考虑不修改中间值的下标，而是让头部下标head1-1乘以这个数。与此同时，还需要修改逆序指标sum2，因为此时尾部元素在逆序里为头部，所以就是让sum2减去head2乘以该数，同样因为要减小对中间值的影响，所以考虑让头部下标head2+1。之后在正序头部插入这个数时，就是让sum2加上尾部下标，即head2加个数乘以这个数。逆序状态的思路类似。（要命了）
所以可以看出，还需要用一个双端队列deque来时刻维护正常的顺序，以及方便快速查出个数来通过head求尾部下标。
最后就是修正答案的部分。观察例子可以发现，不管是sum1还是sum2，下标的改变是与ans不一致的根本原因，所以考虑从下标入手进行修正。而进一步观察可以发现，此时每个数和正确值的差值就是下标偏移量乘以自己。所以通过求这个偏移量，即正确下标1到head的距离，再乘以所有数的累加和sum，再加上sum1或sum2就是正确答案。
总结
H题就是拼尽全力无法战胜了，学的还是不够呜呜……