a
两个指针L、R
R开始指向恰好[R,n]有不超过k个逆序对的地方
随着L的右移，R指针只会右移
逆序对有2部分
1、L左侧与其他位置形成的逆序对
2、R右侧与其他位置形成的逆序对
用树状数组分别维护这两部分
同时维护当前逆序对个数
每次L右移，新的L会增加与L左侧的逆序对和与R右侧的逆序对
每次R右移，R的消失会减少R右侧的逆序对和与L左侧的逆序对
#include<cstdio> #include<algorithm> #define N 100012 using namespace std; int tot; int a[N],hash[N]; int c1[N],c2[N]; int query1(int x) { int sum=0; while(x) { sum+=c1[x]; x-=x&-x; } return sum; } int query2(int x) { int sum=0; while(x) { sum+=c2[x]; x-=x&-x; } return sum; } void add1(int x,int y) { while(x<=tot) { c1[x]+=y; x+=x&-x; } } void add2(int x,int y) { while(x<=tot) { c2[x]+=y; x+=x&-x; } } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); int n,k; long long ans=0,cnt=0; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]),hash[i]=a[i]; sort(hash+1,hash+n+1); tot=unique(hash+1,hash+n+1)-(hash+1); for(int i=1;i<=n;i++) a[i]=lower_bound(hash+1,hash+tot+1,a[i])-hash; int R=n; while(R>=1) { add2(a[R],1); cnt+=query2(a[R]-1); R--; } R++; for(int L=1;L<n;L++) { if(L==R) { cnt=cnt-(L-1-query1(a[R]))-query2(a[R]-1); add2(a[R++],-1); } cnt=cnt+L-1-query1(a[L])+query2(a[L]-1); add1(a[L],1); while(cnt>k && R<=n ) { cnt=cnt-(L-query1(a[R]))-query2(a[R]-1); add2(a[R++],-1); } if(cnt<=k) ans+=n-R+1; } printf("%I64d",ans); }
b
状态压缩式的搜索
但一开始分明是按着DP做的
于是就写出了个又像DP又像bfs的代码
两个结论：
1、成功搞事的前提是 a中除1之外的数 都能由前面的2个数相加得到（可以是2个相同的数）
2、最优解b中的数一定可以是a中的某些数
先判断a是否符合结论1，同时记录a中的每个数可以由哪两个数相加得到
N只有23，将N状态压缩，每一位表示当前状态b中有没有a中的这个数
设state[i][] 表示当前第i次搞事，b中可以有的a的状态
那么state[i][]可以由state[i-1][]转移的条件是
若a[p]+a[q]=a[i] ，state[i-1][]这个状态含有任意一对p、q
所以枚举state[i-1][]中的每一种状态，若这个状态可以转移
不管选哪对p、q，总要用i替换掉这个状态中的某一个位置或者是新增一个位置
替换：设当前状态为j，要替换掉第k位，新的状态为 j^k|i
新增：j^i
最后枚举state[n][]中的每一种状态，1的个数取最少就是答案
优化1：滚动数组
优化2：状态判重，新开一个数组vis[]，int类型，用时间戳的方式判重，避免每次清空
优化3：类似于可行性剪枝，再枚举i-1的状态时，加上
if(minans<当前状态已经用的a的数量) continue;
minans=min(minans,当前状态已经用的a的数量+最多还能用的a的数量);
#include<cstdio> #include<algorithm> #define N 23 using namespace std; int dp[(1<<N)+2]; int n,num[N+1]; int way[N+1][625][2]; int state[2][(1<<N)+2]; int vis[(1<<N)+2]; int sum[(1<<N)+2]; int count(int x) { int cnt=0; while(x) cnt+=x&1,x>>=1; return cnt; } int main() { freopen("b.in","r",stdin); freopen("b.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&num[i]); bool can=false; for(int a=2;a<=n;a++) { can=false; for(int b=0;b<a;b++) for(int c=b;c<a;c++) if(num[a]==num[b]+num[c]) { can=true; way[a][0][0]++; way[a][way[a][0][0]][0]=b; way[a][way[a][0][0]][1]=c; } if(!can) { printf("-1"); return 0; } } int tot=1<<n; for(int i=0;i<tot;i++) sum[i]=count(i); int b,c,j,news; int now=0,last=1; int minans=30; state[1][0]=state[1][1]=1; for(int a=2;a<=n;a++) { state[now][0]=0; for(int k=1;k<=state[last][0];k++) { j=state[last][k]; if(minans<sum[j]) continue; minans=min(minans,sum[j]+n-a+1); can=false; for(int i=1;i<=way[a][0][0];i++) { b=way[a][i][0]; c=way[a][i][1]; if((j & 1<<b-1) && (j & 1<<c-1)) { can=true; break; } } if(!can) continue; for(int i=1;i<=n;i++) if(j & 1<<i-1) { news=j ^ 1<<i-1 | 1<<a-1; if(vis[news]!=a) { state[now][++state[now][0]]=news; vis[news]=a; } } news=j ^ 1<<a-1; if(vis[news]!=a) { state[now][++state[now][0]]=news; vis[news]=a; } } swap(now,last); } int ans=30; for(int i=1;i<=state[last][0];i++) ans=min(ans,sum[state[last][i]]); printf("%d",ans); }
c
所有球无论怎么碰撞，他们的顺序不变
所以先对所有的小球排序
然后枚举相邻两个小球，计算出即将最早碰撞的两个球所需时间t
让所有的球都移动t时间，改变两个球的速度
重复枚举直到没有球会发生碰撞或超过时间
#include<cmath> #include<cstdio> #include<algorithm> using namespace std; struct node { int m,id; double x,v; }e[11]; bool cmp(node p,node q) { return p.x<q.x; } bool cmp2(node p,node q) { return p.id<q.id; } double v1(int i,int j) { return ((e[i].m-e[j].m)*e[i].v+2*e[j].m*e[j].v)/(e[i].m+e[j].m); } double v2(int i,int j) { return ((e[j].m-e[i].m)*e[j].v+2*e[i].m*e[i].v)/(e[i].m+e[j].m); } int main() { freopen("c.in","r",stdin); freopen("c.out","w",stdout); int n,k; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%lf%lf%d",&e[i].x,&e[i].v,&e[i].m),e[i].id=i; sort(e+1,e+n+1,cmp); int a,b; double delta,now,tmp,va,vb ; while(1) { delta=2e9; for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) { if(e[i].v>0 && e[j].v>0 && e[i].v<e[j].v) continue; if(e[i].v<0 && e[j].v>0) continue; if(e[i].v<0 && e[j].v<0 && e[i].v<e[j].v) continue; tmp=(e[j].x-e[i].x)/(e[i].v-e[j].v); if(tmp<delta) delta=tmp,a=i,b=j; } if(now+delta>k) break; for(int i=1;i<=n;i++) e[i].x+=delta*e[i].v; va=v1(a,b); vb=v2(a,b); e[a].v=va; e[b].v=vb; now+=delta; } delta=k-now; for(int i=1;i<=n;i++) e[i].x+=delta*e[i].v; sort(e+1,e+n+1,cmp2); for(int i=1;i<=n;i++) printf("%.3lf ",e[i].x); }