四个题的题解
第一题
我们可以明显发现要构造的字符串是没有重叠的(形如yuy)，也就是互不影响
那么我们首先需要判断是否是满足最小的数量3*k与n的关系(也就是无解的情况)
接着就直接先构造出来所有的串，后面全部接上'u'
// 数学公式要变形
// 莫急莫急先读题
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define endl "\n"
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x) fixed<<setprecision(x)// c++ 保留小数
#define int long long
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N=1000010,M=1010,F=2*N,INF=0x3f3f3f3f,pp=13331,mod=1e9+7;
const double pai=acos(-1.0);// pai
int t,n,m;
void solve()
{
cin>>n>>m;
if(3*m>n){
cout<<-1<<endl;
return ;
}
for(int i=0;i<m;i++) cout<<"you";
for(int i=0;i<n-3*m;i++) cout<<'u';
return ;
}
// 万事读题为先
signed main ()
{
ios// 不能有printf puts scanf
solve();
}
第二题
我们和明显的会想到只要a,b中出现了3的倍数就一定是满足要求的，很多人会直接写
n/3*2
但是明显的会有重复，首先对于一个正好是3的倍数的数，考虑题目要求是a,b都是正整数那么0和n是不满足题目意思的
此时答案会变成(n-1)/3*2,
但是依旧有问题接着就是当一个数是3的倍数我们可以发现(比如9) 3 的对面是6,6的对面是3 也就是我们重复算了这个时候的答案，
那么正解也就呼之欲出了
// 数学公式要变形
// 莫急莫急先读题
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define endl "\n"
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x) fixed<<setprecision(x)// c++ 保留小数
#define int long long
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N=1000010,M=1010,F=2*N,INF=0x3f3f3f3f,pp=13331,mod=1e9+7;
const double pai=acos(-1.0);// pai
int t,n,m;
void solve()
{
cin>>n;
int ans=n/3*2;
if(n%3==0) {
ans=(n-1)/3;
}
cout<<ans<<endl;
return ;
}
// 万事读题为先
signed main ()
{
ios// 不能有printf puts scanf
solve();
}
第三题
解法一
我们可以发现由于变化的次数太多了且都是区间操作我们是没有办法直接维护每一个数的值的，但是我们
发现题目有一句话就是最小的值是与0取max,那么当我们一堆数被减成0之后就是同呼吸共命运了，他们变化
的值是一样的也就是说我们可以对整个数组进行排序处理接着每一次都记录下来哪些数被减成0了以及记录出来
没有变成0的数的变化的数量.
举个例子
5 2
1 2 3 4 5
2 2
1 1
第一次操作是每一个数都要减少2，我就排序之后枚举左端点初始的值是否是大于此时的变化值比如2 2
之后左边的下标就移动到了第二个位置然后一个值来记录变成0 之后的变化量，右边大于0的变化值
注意的是小于0的数的值的变化是一定大于等于0的
// 数学公式要变形
// 莫急莫急先读题
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define endl "\n"
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x) fixed<<setprecision(x)// c++ 保留小数
#define int long long
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N=1000010,M=1010,F=2*N,INF=0x3f3f3f3f,pp=13331,mod=1e9+7;
const double pai=acos(-1.0);// pai
int t,n,m;
int a[N];
void solve()
{
cin>>n>>m;
vector<int> a(n+1,0);
for(int i=1;i<=n;i++) cin>>a[i];
sort(a.begin()+1,a.end());
int addl=0,addr=0,r=0;
while(m--){
int op,x;
cin>>op>>x;
if(op==1) addl+=x,addr+=x;
else{
addl-=x,addr-=x;
while(r+1<=n&&a[r+1]+addr<0) r++;//表示不满足的数是比r小的数
if(addl<0) addl=0;
}
}
int sum=0;
for(int i=r+1;i<=n;i++) sum=(sum+a[i])%mod;
sum=(sum+addr%mod*(n-r)%mod+addl%mod*r%mod)%mod;
cout<<sum<<endl;
return ;
}
// 万事读题为先
signed main ()
{
ios// 不能有printf puts scanf
solve();
}
解法2
我们可以考虑把中间的所有影响和2为1，那么如何处理呢？
我们可以发现初始的时候的值是固定的，那么我要想要他变成0，我只要记录在变化的过程中变化的最小
值，同时维护最后变化的值，如果这个位置的数+变化的最小值还是大于0那么整个过程中是没有小于0
出现过的，可以自己稍微思考一下，同时如果是小于0的表示出现过小于0的情况，注意这个时候原来的数
会变成0，但是我们维护的最终变化值是在有最小变化的值的影响下的，也就是说在经历过最小值的变化之后得到了现在的值
那么整个最小值之后的变化值才是我这个数的变化值
我举个例子
-10 3 4 -2这个变化过程中 最小值是-10，最后的值是-5 但是有的数在-10 之后就是0了后面的对他来说都是重新累加，
-10的影响消失了也就是这个数是变成了(-5-(-10)) 也就是5
// 数学公式要变形
// 莫急莫急先读题
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define endl "\n"
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x) fixed<<setprecision(x)// c++ 保留小数
#define int long long
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N=1000010,M=1010,F=2*N,INF=0x3f3f3f3f,pp=13331,mod=1e9+7;
const double pai=acos(-1.0);// pai
int t,n,m;
int a[N];
void solve()
{
cin>>n>>m;
vector<int> a(n);
for(auto&v:a) cin>>v;
int sum=0,mi=0;
while(m--){
int op,x; cin>>op>>x;
sum+=op==1?x:-x;
mi=min(mi,sum);
}
int ans=0;
for(auto&v:a){
if(v+mi>=0) ans=(ans%mod+v%mod+sum%mod)%mod;
else ans=(ans+(sum-mi)%mod)%mod;
}
cout<<ans<<endl;
return ;
}
// 万事读题为先
signed main ()
{
ios// 不能有printf puts scanf
solve();
}
第四题
第四题是一个模拟题需要按照题目的意思取模拟，我们可以使用stl容器来辅助，关于领地的合并我们可以使用并查集来维护
我们需要判断每一个位置是哪一个人的，以及一个人有多少个串，冲突的处理，(注意并查集的合并的位置)(细心)详情请看代码
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
map<PII,string> belong;// 表示这个点的属于谁
map<string,PII> now;// 表示我现在在哪里
map<string,int> cnt;// 表示有多少地盘
map<PII,PII> p;//表示是一个的联通块 用并查集来维护？
int n,m,k,q;
PII find(PII x){
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}// 用点来连接点
int main(){
cin>>n>>m>>k;
while(k--){
string str;
int x,y;
cin>>str>>x>>y;
now[str]={x,y};// 表示我加入这个点
if(belong.count({x,y})){// 如果这个点有所属
string yuan=belong[{x,y}];// 找到这个
if(str>yuan){// 表示我与这个人争夺这个点
cnt[str]=1;// 表示我赢了
now.erase(yuan);// 他被out
belong[{x,y}]=str;// 表示我赢了这个点属于我
}
else now.erase(str);// 表示我out
}
else{
p[{x,y}]={x,y};// 表示这是一个新的点
belong[{x,y}]=str;// 这个点是我的
cnt[str]=1;
}
}
cin>>q;
while(q--){
string str; char s;
cin>>str>>s;
if(!now.count(str)){// 表示这个点被用过了
cout<<"unexisted empire."<<endl;
continue;
}
auto [x,y]=now[str];// 取出来
if(s=='W') x--;
else if(s=='S') x++;
else if(s=='A') y--;
else y++;
if(x<1||x>n||y<1||y>m){
cout<<"out of bounds!"<<endl;
continue;
}
if(!belong.count({x,y})){// 这是一个新的点
cout<<"vanquish!"<<endl;
belong[{x,y}]=str;// 表示这个点属于我
p[{x,y}]=now[str];// 表示现在这个点的祖宗节点是我原来走的路
now[str]={x,y};// 我现在的状态是
cnt[str]++;// 有新的加入
continue;
}
else{// 表示有人坐在这
string yuan=belong[find({x,y})];
if(yuan==str){
cout<<"peaceful."<<endl;
now[str]={x,y};
continue;
}
if(cnt[str]>cnt[yuan]||(cnt[str]==cnt[yuan]&&str>yuan)){
cout<<str<<" wins! "<<endl;
cnt[str]+=cnt[yuan];
auto fay=find({x,y});// 表示原来的祖先
p[fay]=now[str];
now.erase(yuan);
now[str]={x,y};
continue;
}
else{
auto fan=find(now[str]);
p[fan]=now[yuan];
cnt[yuan]+=cnt[str];
now.erase(str);
cout<<yuan<<" wins! "<<endl;
continue;
}
}
}
return 0;
}
京公网安备 11010502036488号