A
题意：求a *2或者*3 最少多少次能到b
题解：dfs直接判
#include <bits/stdc++.h>
#define maxn 300000+5
using namespace std;
typedef long long int ll;
int n,m,flag=0,ans=-1;
void dfs(int x,int d){
if(flag||x>m)return ;
if(x==m){
ans=d;
flag=1;
return;
}
dfs(x*2,d+1);
dfs(x*3,d+1);
}
int main(){
scanf("%d%d",&n,&m);
dfs(n,0);
printf("%d",ans);
// while(1)getchar();
} B
题意：最长的连续1串
题解：注意一点首尾是相连的，直接多扫一遍就可以
#include <bits/stdc++.h>
#define maxn 300000+5
using namespace std;
typedef long long int ll;
int a[maxn];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
int tmp=0,ans=0;int flag=0;
for(int i=0;i<n;i++){
if(a[i]==1)tmp++;
else tmp=0;
ans=max(tmp,ans);
if(i==n-1&&!flag){
flag=1;
i=-1;
}
}
printf("%d",ans);
// while(1)getchar();
} C
题意：给出每两个相邻元素之间的差，让你构造出序列
题解：直接把第一个设置为1 然后构造出之后 如果有负数每个都加上弥补过来
注意一点不要用数组标记，会re（血和泪的教训）
#include <bits/stdc++.h>
#define maxn 300000+5
using namespace std;
#define INF 0x3f3f3f3f
typedef long long int ll;
int a[maxn];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<n;i++){
scanf("%d",&a[i]);
}
vector<int>v;
v.push_back(1);
int minm=INF;
for(int i=1;i<n;i++){
v.push_back(v[i-1]+a[i]);
minm=min(v[i-1]+a[i],minm);
}
int flag=0;
set<int>s;
for(int i=0;i<n;i++){
if(minm<=0)
v[i]+=(-minm+1);
s.insert(v[i]);
}
set<int>::iterator it=s.end();
it--;
if(s.size()==n&&*s.begin()==1&&*it==n)
for(int i=0;i<n;i++){
printf("%d ",v[i]);
}else printf("-1");
//while(1)getchar();
} D
题意：l字符串和r字符串 的 相同字母可以搭配成一对 ？可以随意搭配 问最多搭配多少对
题解：模拟一下这个过程，我模拟的方法是 把l字符串和r字符串的每个字母的位置分别哈希一下，用的时候再拿出来
不够的用问号补
#include <bits/stdc++.h>
#define maxn 150000+5
using namespace std;
#define INF 0x3f3f3f3f
typedef long long int ll;
int vis1[maxn],vis2[maxn];
int w1=0,w2=0;
struct node{
char c;
int id;
};
vector<int>a[30],b[30];
vector<int>wl,wr;
int ansu[maxn],ansv[maxn],flag=0;
int main(){
int n;cin>>n;
//cout<<int('?'-'a')<<endl;
string l,r;
cin>>l>>r;
for(int i=0;i<n;i++){
if(l[i]!='?')
a[l[i]-'a'].push_back(i+1);
else wl.push_back(i+1);
if(r[i]!='?')
b[r[i]-'a'].push_back(i+1);
else wr.push_back(i+1);
}
for(int i=0;i<26;i++){
int j;
for( j=0;j<min(a[i].size(),b[i].size());j++){
ansu[flag]=a[i][j];ansv[flag++]=b[i][j];
a[i][j]=-1;b[i][j]=-1;
}
if(a[i].size()<b[i].size()&&w1<wl.size()){
for(;j<b[i].size()&&w1<wl.size();j++){
ansu[flag]=wl[w1++];
ansv[flag++]=b[i][j];
}
}else if(a[i].size()>b[i].size()&&w2<wr.size()){
for(;j<a[i].size()&&w2<wr.size();j++){
ansu[flag]=a[i][j];
ansv[flag++]=wr[w2++];
}
}
}
while(w1<wl.size()&&w2<wr.size()){
ansu[flag]=wl[w1++];
ansv[flag++]=wr[w2++];
}
printf("%d\n",flag);
for(int i=0;i<flag;i++){
printf("%d %d\n",ansu[i],ansv[i]);
}
//while(1)getchar();
} E
题意：每次攻击耗时一分钟 一轮n次攻击 给你一轮每次攻击减少的血量 问你多少分钟h<=0
题解：先求一下第一轮能不能杀死，能杀死直接输出
如果不能杀死，判断一轮一下来 生命增加还是减少 ，如果增加输出-1
然后 求一下(H+maxm(每轮扣除的最大生命))/sum 这是死之前的轮数
最后一轮模拟一下 分钟加起来就是答案
#include <bits/stdc++.h>
#define maxn 200000+5
using namespace std;
#define INF 0x3f3f3f3f
typedef long long int ll;
ll a[maxn];
int main(){
ll h, n;
scanf("%lld%lld",&h,&n);
ll sum=0; ll minm=1e12+5;
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
sum+=a[i];
minm=min(sum,minm);
if(h+sum<=0){
printf("%d",i+1);
//while(1)cout<<233<<endl;
return 0;
}
}
if(sum>=0){
printf("-1");
return 0;
}
sum=-sum;
ll ans=0;
ans+=((h+minm)/sum)*n;
h-=((h+minm)/sum)*sum;
for(int i=0;h>0;i++){
h+=a[i];
ans++;
if(i==n-1)i=-1;
}
printf("%lld",ans);
//while(1)getchar();
} F1/F2（题解一样）
题意：求 和一样 的 最大区间数
题解：暴力求一下区间数，用map 记录和一样的区间数
然后对每一个sum 求一下区间覆盖，找区间最多的sum
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
const int maxn=1500+7;
ll d[maxn],pre[maxn];
int n;
struct block{
int i,j;
block(int i=0,int j=0):i(i),j(j){}
bool operator<(const block &rhs)const{
if(j!=rhs.j)return j<rhs.j;
return i<rhs.i;
}
}bs[maxn*maxn];
map<ll ,vector<block> > m;
int counta(ll sum){
vector<block> curuse=m[sum];
vector<block> newuse;
sort(curuse.begin(),curuse.end());
int last=-1,ans=0;
for(auto a:curuse){
if(last<a.i){
ans++;
last=a.j;
newuse.push_back(a);
}
}
m[sum]=newuse;
return ans;
}
int main()
{
scanf("%d",&n);
m.clear();
for(int i=1;i<=n;i++)scanf("%lld",&d[i]);
pre[0]=0;
for(int i=1;i<=n;i++)pre[i]=pre[i-1]+d[i];
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++){
m[pre[j]-pre[i-1]].push_back(block(i,j));
}
int maxx=-1;
ll ans;
for(auto a:m){
ll o=a.first;
int u=counta(o);
// cout<<u<<endl;
if(u>maxx){
ans=a.first;
maxx=u;
}
}
cout<<maxx<<endl;
for(auto a:m[ans]){
cout<<a.i<<" "<<a.j<<endl;
}
return 0;
} G
题意：让你对每条边进行边染色，如果某个点周围的边有重复的颜色 说明这个点 是 坏的 ，问你让坏的点小于等于k个 最少用多少种颜色
题解：对于每个点来说 如果想让他是好的 那度数=颜色数 所以 保证前n-k个点是好的就行了 所以最大颜色数就是按照度数从小到大排序的 第n-k-1个点的度数
最后直接dfs 每条边，染上色就是了，颜色不要超过之前求得颜色（比较难写。。。我写了三个vector。。。）
#include <bits/stdc++.h>
#define maxn 200000+5
using namespace std;
int n,k,ans;
int d[maxn],vis[maxn];
struct node {
int id,d;
int u,v,c;
};
vector<node>ansg;
vector<node>v;
vector<node>G[maxn];
bool cmp(node a,node b){
return a.d<b.d;
}
bool cmp2(node a,node b){
return a.id<b.id;
}
void dfs(int x,int last){
int flag=1;
for(int i=0;i<G[x].size();i++){
int u=x,v=G[x][i].d;
if(!vis[v]){
if(flag==last&&flag<ans)flag++;
//cout<<ans<<endl;
node tmp;tmp.id=G[x][i].id;tmp.c=flag;tmp.u=u;tmp.v=v;
ansg.push_back(tmp);
//<<tmp.v<<endl;
vis[v]=1;
dfs(v,flag);
if(flag<ans)flag++;
}
}
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n-1;i++){
int u,v;
scanf("%d%d",&u,&v);
d[u]++,d[v]++;
node tmp;tmp.id=i;tmp.d=v;
G[u].push_back(tmp);
tmp.d=u;
G[v].push_back(tmp);
}
for(int i=1;i<=n;i++){
node tmp;tmp.d=d[i],tmp.id=i;
v.push_back(tmp);
}
sort(v.begin(),v.end(),cmp);
ans=v[n-k-1].d;
cout<<ans<<endl;
vis[v[0].id]=1;
//cout<<v[0].id<<endl;
dfs(v[0].id,1);
sort(ansg.begin(),ansg.end(),cmp2);
//cout<<ansg.size()<<endl;
for(int i=0;i<ansg.size();i++)
cout<<ansg[i].c<<" ";
//while(1)getchar();
}
京公网安备 11010502036488号