当前位置：网站首页>2022/8/3
2022/8/3
2022-08-04 22:48:00 【killer_queen4804】
活动地址：CSDN21天学习挑战赛
Problem - 1326D1 - Codeforces双指针
很明显我们要设l，r分别作为头尾指针，如何s[l]==s[r],就r--,l++,如不等就要分开考虑了，分别枚举l和r就行，一开始我这脑子竟然还想要双重循环暴力，，，
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+5;
ll t;
string s;
bool pd(string ss){
string s2=ss;
reverse(ss.begin(), ss.end());
return s2==ss;
}
int main(){
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--){
cin>>s;
ll ans=0;
string tmp;
string res;
string sl="",sr="";
ll l=0,r=s.size()-1;
while(l<=r){
if(s[l]==s[r]){
if(l<r){
sl+=s[l];sr=s[r]+sr;
l++;r--;
}
else{
sl+=s[l];l++;
}
tmp=sl+sr;
if(ans<tmp.size()){
ans=tmp.size();
res=tmp;
}
}
else{
ll x=l;string sx=sl;
while(x<r){
sx+=s[x];
tmp=sx+sr;
// cout<<tmp<<" "<<x<<" "<<sx<<endl;
if(pd(tmp)){
if(ans<tmp.size()){
ans=tmp.size();
res=tmp;
}
}
x++;
}
ll y=r;string sy=sr;
while(y>l){
sy=s[y]+sy;
tmp=sl+sy;
if(pd(tmp)){
if(ans<tmp.size()){
ans=tmp.size();
res=tmp;
}
}
y--;
}
break;
}
}
cout<<res<<endl;
}
system("pause");
return 0;
}
1371D - Grid-00100
只要看出规律来就好办了，最好的贪心方式就是一开始先填对角线的，然后每次位置加1即可，这题竟然1600，，，
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+5;
ll t,n,k,a[305][305],b[305],r[305],c[305];
int main(){
scanf("%lld",&t);
while(t--){
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) a[i][j]=0;
for(int i=1;i<=n;i++) b[i]=i,r[i]=c[i]=0;
ll x=1;
while(k){
a[x][b[x]]=1;
b[x]++;
if(b[x]>n) b[x]=1;
x++;
if(x>n) x=1;
k--;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
r[i]+=a[i][j];
c[j]+=a[i][j];
}
}
ll maxr=0,minr=1e18,maxc=0,minc=1e18;
for(int i=1;i<=n;i++){
// cout<<r[i]<<" "<<c[i]<<" "<<i<<endl;
maxr=max(maxr,r[i]);minr=min(minr,r[i]);
maxc=max(maxc,c[i]);minc=min(minc,c[i]);
}
printf("%lld\n",(maxr-minr)*(maxr-minr)+(maxc-minc)*(maxc-minc));
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) printf("%lld",a[i][j]);
printf("\n");
}
}
system("pause");
return 0;
}
P3521 [POI2011]ROT-Tree Rotations - 洛谷 | 线段树合并
可以看成是每个叶节点就是一个权值线段树，合并左右子树只会对跨子树的逆序对产生影响，所以合并时取交换前和交换后的最小值就可以了，这题另外一个难点可能就是输入了，，
题解 P3521 【[POI2011]ROT-Tree Rotations】 - 一个NSOIer的博客 - 洛谷博客
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5+5;
ll n,cnt,u,v,ans;
struct node{
ll l,r,size;
}t[N*20];
void pushup(ll p){t[p].size=t[t[p].l].size+t[t[p].r].size;}
ll update(ll l ,ll r,ll k){
ll p=++cnt;
if(l==r){t[p].size++;return p;}
ll mid=l+r>>1;
if(k<=mid) t[p].l=update(l,mid,k);
else t[p].r=update(mid+1,r,k);
pushup(p);
return p;
}
ll merge(ll x,ll y,ll l,ll r){
if(!x||!y) x|=y;
else if(l==r){t[x].size+=t[y].size;}
else{
u+=t[t[x].r].size*t[t[y].l].size;//交换前的逆序对数
v+=t[t[x].l].size*t[t[y].r].size;//交换后的逆序对数
ll mid=l+r>>1;
t[x].l=merge(t[x].l,t[y].l,l,mid);//继续向下面操作，合并左右子节点
t[x].r=merge(t[x].r,t[y].r,mid+1,r);
pushup(x);
}
return x;
}
ll dfs(){
ll val,p;
scanf("%lld",&val);
if(val) p=update(1,n,val);
else{
ll ls=dfs(),rs=dfs();//获取左右子树的根节点
u=0,v=0;
p=merge(ls,rs,1,n);//合并左右子树
ans+=min(u,v);
}
return p;
}
int main(){
scanf("%lld",&n);
dfs();
printf("%lld\n",ans);
system("pause");
return 0;
}
P3224 [HNOI2012]永无乡 - 洛谷 | 线段树合并
第一次自己做出合并的题目来，并查集维护连通性的同时进行线段树的合并，每个岛就是一棵线段树，查询的时候也是直接查自己的祖先，即findd(x)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5+5;
ll n,m,cnt,s[100005],rt[300005],ma[100005];
ll findd(ll x){return x==s[x]?x:s[x]=findd(s[x]);}
struct node{
ll l,r,val;
}t[N*20];
void pushup(ll p){t[p].val=t[t[p].l].val+t[t[p].r].val;}
void update(ll l,ll r,ll &p,ll k){
if(!p) p=++cnt;
if(l==r){t[p].val++;return;}
ll mid=l+r>>1;
if(k<=mid) update(l,mid,t[p].l,k);
else update(mid+1,r,t[p].r,k);
pushup(p);
}
void merge(ll &x,ll y){
if(!x||!y) x|=y;
else{
t[x].val+=t[y].val;
merge(t[x].l,t[y].l);
merge(t[x].r,t[y].r);
pushup(x);
}
}
ll query(ll l,ll r,ll p,ll k){
if(l==r) return l;
ll mid=l+r>>1;
if(k<=t[t[p].l].val) return query(l,mid,t[p].l,k);
else return query(mid+1,r,t[p].r,k-t[t[p].l].val);
}
int main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){
ll x;
scanf("%lld",&x);
update(1,n,rt[i],x);
ma[x]=i;
s[i]=i;
}
for(int i=1;i<=m;i++){
ll u,v;
scanf("%lld%lld",&u,&v);
ll x=findd(u),y=findd(v);
if(x==y) continue;
s[y]=x;
merge(rt[x],rt[y]);
}
// cout<<t[rt[1]].val<<" "<<s[1]<<" "<<s[2]<<endl;
ll q;
scanf("%lld",&q);
while(q--){
char ch[3];
ll x,y;
scanf("%s%lld%lld",ch,&x,&y);
if(ch[0]=='Q'){
ll ans=0;
if(x<1||t[rt[findd(x)]].val<y||x>n){printf("-1\n");continue;}
ans=query(1,n,rt[findd(x)],y);
printf("%lld\n",ma[ans]);
}
else{
ll xx=findd(x),yy=findd(y);
if(xx==yy) continue;
s[yy]=xx;
merge(rt[xx],rt[yy]);
}
//cout<<t[rt[1]].val<<" sss"<<endl;
}
system("pause");
return 0;
}
P1600 [NOIP2016 提高组] 天天爱跑步 - 洛谷 | 线段树合并
每个人的路径要是一个一个看的话时间复杂度太高了，考虑树上差分，这样考虑两个端点就可以了，一般的情况下，一般都是s->lca,然后再lca->t,先考虑s,假设dep[j]<dep[s](不然也没啥好看的，这个人一定不经过j了),则有
dep[s]=dep[j]+w[j]，
则在树上的体现就是dep[s]+1,查询的时候只需要查dep[j]+w[j]出现了几次就可以；再考虑t，假设dep[j]>dep[t],则有
（dep[s]-dep[lc])+dep[y]-dep[lc]+w[j]=dep[j];
lc是s,t的lca，因为是从s走过来的，所以要减去s到lca的这段,y是深度小于t的点，意思就是从lca->t的过程中有一个点y满足这个式子就可以，最后dfs遍历一遍求出答案就行了
题解 P1600 【天天爱跑步】 - Robin12138 的博客 - 洛谷博客
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5+5;
ll n,m,w[300005];
//链式前向星
ll head[300005],cnt;
struct Edge{
ll from,to,next;
}edge[300005*2];
void addedge(ll from, ll to){
edge[++cnt].from = from;
edge[cnt].to = to;
edge[cnt].next =head[from];
head[from] = cnt;
}
//lca
ll son[300005],f[300005],siz[300005],top[300005],dep[300005];
void dfs1(ll u,ll fa){
siz[u]=1;f[u]=fa;dep[u]=dep[fa]+1;
for(int i=head[u];i;i=edge[i].next){
ll j=edge[i].to;
if(j==fa) continue;
dfs1(j,u);
siz[u]+=siz[j];
if(siz[son[u]]<siz[j]) son[u]=j;
}
}
void dfs2(ll u,ll topx){
top[u]=topx;
if(son[u]) dfs2(son[u],topx);
for(int i=head[u];i;i=edge[i].next){
ll j=edge[i].to;
if(j!=f[u]&&j!=son[u]) dfs2(j,j);
}
}
ll lca(ll x,ll y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=f[top[x]];
}
return dep[x]<dep[y]?x:y;
}
//线段树
ll rt[600005],ct,ans[300005];
struct node{
ll l,r,val;
}t[600005*40];
void pushup(ll p){t[p].val=t[t[p].l].val+t[t[p].r].val;}
void update(ll l,ll r,ll &p,ll k,ll v){
if(!p) p=++ct;
if(l==r){t[p].val+=v;return;}
ll mid=l+r>>1;
if(k<=mid) update(l,mid,t[p].l,k,v);
else update(mid+1,r,t[p].r,k,v);
pushup(p);
}
void merge(ll &x,ll y,ll l,ll r){//检查了半天没加取址符号，我这个老六
if(!x||!y) x|=y;
else if(l==r) t[x].val+=t[y].val;
else{
ll mid=l+r>>1;
merge(t[x].l,t[y].l,l,mid);
merge(t[x].r,t[y].r,mid+1,r);
pushup(x);
}
}
ll query(ll l,ll r,ll p,ll k){
if(l==r) return t[p].val;
ll mid=l+r>>1;
if(k<=mid) return query(l,mid,t[p].l,k);
else return query(mid+1,r,t[p].r,k);
}
void dfs(ll u){
for(int i=head[u];i;i=edge[i].next){
ll j=edge[i].to;
if(j==f[u]) continue;
dfs(j);
merge(rt[u],rt[j],1,n<<1);
}
if(w[u]&&n+dep[u]+w[u]<=2*n) ans[u]+=query(1,n<<1,rt[u],n+dep[u]+w[u]);
ans[u]+=query(1,n<<1,rt[u],n+dep[u]-w[u]);
}
int main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<n;i++){
ll u,v;
scanf("%lld%lld",&u,&v);
addedge(u,v);addedge(v,u);
}
dfs1(1,0);dfs2(1,1);
for(int i=1;i<=n;i++) scanf("%lld",&w[i]);
for(int i=1;i<=m;i++){
ll x,y;
scanf("%lld%lld",&x,&y);
ll lc=lca(x,y);
//cout<<"ssss"<<endl;
update(1,n<<1,rt[x],n+dep[x],1);
update(1,n<<1,rt[y],2*dep[lc]-dep[x]+n,1);
//(dep[y]-dep[lc])-dep[lc]-(dep[x]-dep[lc])=dep[j]-w[j];
update(1,n<<1,rt[lc],n+dep[x],-1);
update(1,n<<1,rt[f[lc]],2*dep[lc]-dep[x]+n,-1);
}
dfs(1);
for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
system("pause");
return 0;
}
边栏推荐
猜你喜欢
随机推荐
【3D建模制作技巧分享】ZBrush纹理贴图怎么导入
Reconfigure the ffmpeg plugin in chrome
360市值四年蒸发3900亿，政企安全能救命吗？
ES 数据聚合、数据同步、集群
【游戏建模模型制作全流程】在ZBrush中雕刻恶魔城男性角色模型
VSCode - common shortcut keys (continuous recording
Qt中的常用控件
How to make a video gif?Try this video making gif artifact
Redis understanding
postman接口测试
ANT1.7下载以及配置方法
限制tensorflow使用Cpu核数
线上虚拟展馆展示具有哪些优势
VC bmp文件总结
力扣24-两两交换链表中的节点——链表
【字符串函数内功修炼】strncpy + strncat + strncmp（二）
SSM整合完整流程讲解
【TCP/IP 四 IP 网际协议】
【3D建模制作技巧分享】ZBrush模型制作流程：地精
panic: reflect: reflect.Value.SetString using value obtained using unexported field