当前位置 博文首页 > srh20的博客：牛客练习赛88 补题
思路：
先要满足位数最多，再满足在前面的数尽量大
I:1 II:2 III:3 IV:4 V:5 VI:6 VII:7 VIII:8
致分为两种情况：
总体都需要注意的是：凑完剩下的数的个数一定要>=n-1;
(1)有V：凑8，凑7，凑6，凑5，因为只要能凑4，肯定能凑6，那必然是选择大一点的6啊
(2)没有V：凑3，凑2，凑1
考察：贪心
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void rd(long long &x){//快读
char c;
for (x=0,c=getchar();c<48;c=getchar());
for (;c>47;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
}
void solve(){
ll a,b,n;
ll ans=0;
rd(a),rd(b),rd(n);
if((a+b)<=n){//如果V和I的个数之和小于等于n，那么依次输出，5放前面
for(int i=1;i<=a;i++) printf("5");
for(int i=1;i<=b;i++) printf("1");
}
else{
ll sum=a+b;//V和I的个数之和
while(n){
if(a>=1){//如果有V
if(b-3>=0&&(sum-4)>=(n-1)){//如果够凑VIII：8，并且保证剩下的个数总和>=n-1
printf("8");
a--,b-=3,sum-=4;
n--;
}
else if(b-2>=0&&(sum-3)>=(n-1)){//如果够凑VII：7，并且保证剩下的个数总和>=n-1
printf("7");
a--,b-=2,sum-=3;
n--;
}
else if(b-1>=0&&(sum-2)>=(n-1)){//如果够凑VI：6，并且保证剩下的个数总和>=n-1
printf("6");
a--,b-=1,sum-=2;
n--;
}
else if(b==0||sum==n){//如果没有I了，就输出5
printf("5");
a--,sum--;
n--;
}
}
else if(a==0){//如果没有V
if(b>=3&&(sum-3)>=(n-1)){//如果够凑3并且保证剩下的个数>=n-1
printf("3");
b-=3,sum-=3,n--;
}
else if(b>=2&&(sum-2)>=(n-1)) {//如果够凑并2且保证剩下的个数>=n-1
b-=2,sum-=2,n--;
printf("2");
}
else if(b==1||sum==n){//够凑1
b--,sum--,n--;
printf("1");
}
}
}
}
puts("");//换行
}
int main(){
int t;
scanf("%d",&t);
while(t--){
solve();
}
return 0;
}
思路：
若 C 可以由 M 截取其中 K 个连续字符并放到最末尾得到。
等价于 ：C和M均去掉M末尾的K个字符的序列之后，得到的字符串相同。
因为 K个字符的序列 在M中可能有多处，但是只要有一处满足就可以证明
C 可以由 M 截取其中 K 个连续字符并放到最末尾得到。
先特判：
(1)如果M串和C串长度不等，肯定不行。
(2)如果串的长度都小于k了，肯定也不行。
(3)如果两串相同并且截取的刚好是整个串，必定可以
others:
先获取C末尾的长度为K的子序列，并且将C的这个子序列从C中删除。
在M中查找这个子序列出现的所有位置pos，每次令一个新的串s=M,
删除掉这个位置之后的长度为K的子串，然后比较s和C，如果相同，
那么可以。
考察： 字符串
传送门：查找子串在母串中的位置
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool check(string m,string c,int k){
int a=m.size(),b=c.size();//分别获得m串的长度，c串的长度
if(a!=b) return false;
if(a<k) return false;
if(m==c&&k==a) return true;
string s1= c.substr(b-k);
string s= c.substr(0,b-k);
int pos = 0;
int i=1;
while((pos=m.find(s1,pos))!=string::npos){//获得m中所有子串s1的位置
string oo = m;//令一个新的串等于m
oo.erase(pos,k);//删除掉这个位置后的长度为K的序列
pos++;//移动到下一个位置寻找
if(oo==s) return true;//只要找到一种情况满足就行
}
return false;
}
void solve(){
string m,c;
int k;
cin>>m>>c>>k;
if(check(m,c,k)) puts("YES");
else puts("NO");
}
int main(){
int t;
scanf("%d",&t);
while(t--){
solve();
}
return 0;
}
思路：
异或：不同为1 同或：相同为1
我们发现同或其实就是异或完取反K位 。
所以不管怎样都需要先异或，最后再来取反并比较大小。
因为每次只有取反和不取反两种操作，因此最后异或(2^k-1) 。
考察：异或，同或
Notice:
因为1≤k≤64，2^k可能会很大，因此需要用到unsigned long long
代码如下：
(1)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;//一定要用 unsigned long long
int n,k;
ull s,a;
ull qk(ull a,ull b){//快速幂
ull ans=1;
while(b){
if(b&1) ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}
void solve(){
scanf("%d%d",&n,&k);
//因此，不管怎么样，都是要先异或
while(n--){
scanf("%llu",&a);
s^=a;
}
ull p = qk(2
