水
#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1e3+;
struct node{
ll num,mag;
friend bool operator <(const node &a,const node &b){
return a.mag>b.mag;
}
}a[maxn];
int n;
ll p[];
ll add(ll x,ll val){
for(int i=;i>=;i--)
{
if(x&(<<i))
{
if(!p[i]){
p[i]=x;
break;
}else{
x=x^p[i];
}
}
}
if(x>)return val;
return ;
}
int main(){
while(cin>>n)
{
ll l,r,d;
while(n--)
{
cin>>l>>r>>d;
if(d<l)printf("%lld\n",d);
else{
printf("%lld\n",(r/d+)*d); }
}
}
}
小模拟，从前往后扫到第一个 [: ,从后往前扫到第一个 :] ，然后数中间的 “|” 就可以了。
#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=5e5+;
char s[maxn];
int main(){
while(scanf("%s",s+)!=EOF)
{
int flag=,p1=-,p2=-,len=strlen(s+);
for(int i=;i<=len;i++)
{
if(flag==)
{
if(s[i]=='[')flag=;
}else{
if(s[i]==':'){
p1=i;
break;
}
}
}
flag=;
for(int i=len;i>p1&&i>;i--)
{
if(flag==)
{
if(s[i]==']')flag=;
}else{
if(s[i]==':'){
p2=i;
break;
}
}
}
if(p1==-||p2==-){
printf("-1\n");
continue;
}
int tot=;
for(int i=p1+;i<p2;i++)
{
if(s[i]=='|')tot++;
}
printf("%d\n",tot+);
}
}
题意：把给出的区间分成两部分，使不同部分的区间，不会有交点。
按 l 排序一遍，如果 l 小于前面最大的 r ，则必须和前面分在同一个群，否则就到第二个群。
#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=2e5+;
int T,n;
struct node{
int l,r;
int id;
friend bool operator <(const node &a,const node &b)
{
return a.l<b.l;
}
}a[maxn];
int ans[maxn];
int main(){
cin>>T;
while(T--)
{
cin>>n;
for(int i=;i<=n;i++)
{
scanf("%d%d",&a[i].l,&a[i].r);
a[i].id=i;
}
sort(a+,a++n);
int maxx=a[].r,tep=,flag=;
ans[a[].id]=;
for(int i=;i<=n;i++)
{
if(a[i].l<=maxx){
ans[a[i].id]=+tep;
}else{
ans[a[i].id]=+-tep;
tep=-tep;
flag=;
}
maxx=max(maxx,a[i].r); }
if(flag==)puts("-1");
else{
for(int i=;i<=n;i++)
{
printf("%d%c",ans[i]," \n"[i==n]);
}
}
}
}
题意：给出一颗点带权的数，求任意两点简单路径上的点gcd大于1的长度最大是多少。
题解：
gcd大于1即不互质，若一条路径是合法路径，则必定有一个大于1的公共质因子。所以我们可以对每个小于2e5的质数重新建树，然后再求树的直径。
建图是怎么建的呢，其实只要把边读入的时候，就把边塞到各自的质因子背包里面去，最后把每个背包的边都建立出来，跑树上直径。
但是有一个问题是，小于2e5的质数有一万多个，树的直径又是O（n）的，这样看上去会超时，我也困扰了好久。其实，两个点之间的公共gcd的质因子个数最多就十个左右，（再多就爆了）也就意味着每个点最多被建图十次，所以如果跑树的直径最后的总计算次数也就是10*O（n）左右，不会超时，这类问题以后要注意，明明很快就想到标算的，但迟迟不敢动手。
#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=2e5+;
int prim[maxn],n,u,v,a[maxn];
int gcd(int a,int b){
return b==?a:gcd(b,a%b);
}
void initPrim(){
for(int i=;i<=2e5/;i++)
{
for(int j=;i*j<=2e5;j++)
{
prim[i*j]=;
}
}
}
struct edge{
int u,v;
};
vector<edge>ve[maxn];
vector<int >e[maxn];
vector<int >jont;
bool vis[maxn];
int ans=;
int dfs(int u,int fa,int dep){
vis[u]=;
int f=;
int flink=,slink=;
for(int i=;i<e[u].size();i++)
{
int v=e[u][i];
if(v==fa)continue;
f=;
int tep=dfs(v,u,dep+);
if(tep>flink)slink=flink,flink=tep;
else if(tep>slink)slink=tep;
}
ans=max(ans,max(dep+flink,flink++slink));
return flink+; }
int main(){
initPrim();
while(cin>>n)
{
ans=;
int fff=;
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]>)fff=;
}
for(int i=;i<=2e5;i++)ve[i].clear();
for(int i=;i<n;i++)
{
scanf("%d%d",&u,&v);
int k=gcd(a[u],a[v]);
if(k>){
for(int j=;j*j<=k;j++)
{
if(k%j==)
{
if(j!=&&prim[j]==) ve[j].push_back({u,v});
if(j*j!=k&&prim[k/j]==) ve[k/j].push_back({u,v});
}
}
}
}
if(fff==){
puts("");
continue;
}
clr(vis,);
for(int i=;i<=2e5;i++)
{
if(!prim[i])
{
for(int j=;j<ve[i].size();j++)
{
if(vis[ve[i][j].u]==)
{
jont.push_back(ve[i][j].u);
}
if(vis[ve[i][j].v]==)
{
jont.push_back(ve[i][j].v);
}
vis[ve[i][j].u]=;
vis[ve[i][j].v]=;
e[ve[i][j].u].push_back(ve[i][j].v);
e[ve[i][j].v].push_back(ve[i][j].u);
}
for(int j=;j<jont.size();j++)
{
vis[jont[j]]=;
}
for(int j=;j<jont.size();j++)
{
int u=jont[j];
if(!vis[u]){
dfs(u,,);
}
}
for(int j=;j<jont.size();j++)
{
e[jont[j]].clear();
}
jont.clear();
}
}
cout<<ans<<endl;
}
}
为什么这会是E题，一开始我以为是求有几张钞票能被塞进去，看了样例才发现我想太多了。
反正就钞票放进去的时候，固定格式，短的一边在下面，钱包也是这样，分别记录长边和短边的最大值，比一下即可。
#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=2e5+;
int T,n;
struct node{
int l,r;
int id;
friend bool operator <(const node &a,const node &b)
{
return a.l<b.l;
}
}a[maxn];
int ans[maxn];
int main(){
cin>>T;
int maxl=,maxr=,l,r;
char op[];
while(T--)
{
scanf("%s%d%d",op,&l,&r);
if(op[]=='+'){
if(l>r)swap(l,r);
maxl=max(maxl,l),maxr=max(maxr,r);
}else{
if(l>r)swap(l,r);
if(l>=maxl&&r>=maxr)printf("YES\n");
else puts("NO");
}
}
}
好题，题解移步我的另外一篇博客 点这里
#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=;
ll ans;
int dp[maxn][maxn][maxn],a[maxn];
int n,m;
int main(){
while(cin>>n>>m)
{
ans=;
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
dp[i][j][]=a[j]-a[i];
}
}
for(int k=;k<=n;k++)
{
for(int i=;i<=n;i++)
{
int w=i;
for(int j=i;j<=n;j++)
{
while(w<j&&max(dp[i][w][k-],a[j]-a[w])>max(dp[i][w+][k-],a[j]-a[w+]))w++;
dp[i][j][k]=max(dp[i][w][k-],a[j]-a[w]);
}
}
}
int s,f,r;
ll c;
while(m--)
{
scanf("%d%d%lld%d",&s,&f,&c,&r);
ans=max(ans,dp[s][f][r]*c);
}
cout<<ans<<endl;
}
}
题意：给出一个序列，试将其划分为尽可能多的非空子段，满足每一个元素出现且仅出现在其中一个子段中，且在这些子段中任取若干子段，它们包含的所有数的异或和不能为0．
思路：先处理出前缀异或，这样选择更多的区间其实就相当于选择更多的前缀异或，并且这些前缀异或不能异或出0，这就变成了线性基的基础题了。贪心的放，能放就放。不能放就意味着线性基的add函数里面的val最后变成了0，也就是当前已经插入的线性基已经可以异或出正在插入的数了，所以不能放。
#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=2e5+;
ll a[maxn],p[],s[maxn];
int n;
int add(ll val){
for(int i=;i>=;i--)
{
if(val&(<<i)){
if(!p[i]){
p[i]=val;
return ;
}
val^=p[i];
}
}
return ;
}
int main(){
while(cin>>n)
{
clr(p,);
for(int i=;i<=n;i++)
{
scanf("%lld",&a[i]);
s[i]=s[i-]^a[i];
}
if(s[n]==){
puts("-1");
continue;
}
int ans=;
for(int i=n;i>;i--)
{
ans+=add(a[i]);
}
cout<<ans<<endl;
}
}