Description 有n堆石子，从1~n编号，其石子总数为2^k。 每次可以选择两堆石子a和b，满足a堆的石子数不比b堆的多，记c为a的石子数。然后可以进行以下操作：从b堆石子中拿c这么多的石子到a堆中。 要求你给出一个方案，使得最后有一堆石子的数目达到2^k。
Input 第一行两个正整数n，k。 第二行n个非负数ai。 Output
输出若干行，每行两个数a,b，表示每次操作中的两堆石子的编号，必须满足题中所给的大小关系！
Sample Input
2 2 3 1
Sample Output
2 1 1 2
Hint
【数据规模】 对于30%的数据，n=2； 对于100%的数据，n<=100000，k<=31。 【注释】 此题需要Special Judge。
思路：暴力 要使得最终得到2^k 转成二进制就是只有第一个1，其余都为0 那么就可以利用这个性质，从后向前依次将所有数的最后一位变0（因为当枚举到前面，后面怎么加都是0）
代码：
#include<cstdio> #include<iostream> using namespace std; int n,k,l; long a[100000]; int main() { scanf("%d%d",&n,&k); for (int i=1;i<=n;i++) scanf("%ld",&a[i]); l=0; for (int i=1;i<=k;i++) for (int j=n;j>=1;j--) if ((a[j]&(1<<(i-1)))!=0) if (l==0) l=j; else { if (a[j]>a[l]) { a[j]-=a[l]; a[l]=a[l]<<1; printf("%d %d\n",l,j); l=0; } else { a[l]-=a[j]; a[j]=a[j]<<1; printf("%d %d\n",j,l); l=0; } } return 0; }Description
编号为1~n的n个城市，每个城市有两个权值Ai和Bi。 对于两个城市i和j，i可到j当且仅当j>i，而费用为(j-i)*Ai+Bj。 求从城市1到城市n的最小费用。
Input
第一行一个正整数n。 第二行n个正整数，第i个表示Ai。 第三行n个正整数，第i个表示Bi。
Output
一个数，表示最小的费用。
Sample Input
4 2 9 5 4 9 1 2 2
Sample Output
8
Hint
【数据规模】 对于20%的数据，1<=n<=100； 对于50%的数据，1<=n<=3000； 对于100%的数据，1<=n<=100000，1<=Ai,Bi<=10^9。
思路： ①DP+队列 更新i的状态可以是1~i-1，但是有很多状态是没有用的（永远小），所以弄一个队列存下可能有用的状态 队列：若有两个点j和k（满足j< k），若要k比j优，那么k->i <= j->i，且a[k]<=a[j]，那就可以把k扔掉。每次更新完f[i]就把它加入队尾，然后维护队列。 ②斜率优化+二分 首先，知道f[i]=min(f[j]+(j-i)*a[i]+b[j])，这应该每个人都知道 =min(f[j]+b[j]+j*a[i])-i*a[i] 发现，只有j*a[i]项存在两个不同的值（i和j） 那么类似于这种情况的都可以用斜率优化。 设g[j]=f[j]+b[j] 那么原式=min(g[j]+j*a[i])-i*a[i] 运用方法①的思路，要求出最优的点，如果枚举两个位置j和k,让j,k< i,j< k 那么如果g[j]+j*a[i]< g[k]+k*a[i] =(j-k)*a[i]< g[k]-g[j] =-a[i]<(g[k]-g[j])/(k-j) 然后我们就可以构造出一个单调上升的凸多边形的下壳，那么现在就可以去二分求出一个最优的点，如果当前求出的斜率(g[k]-g[j])/(k-j)>=-a[i]，就将r左移，不然就右移l 在求出一个最优点，再存起来就行了
方法①代码：
#include<cstdio> #include<iostream> using namespace std; long long a[100000],b[100000],f[100000],k[100000]; int n,m,i,j,l,x; long long much(int x,int y) { return f[x]+a[x]*(y-x); } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%lld",&a[i]); for (int i=1;i<=n;i++) scanf("%lld",&b[i]); l=1; for (int i=2;i<=n-1;i++) { if (k[i]!=0&&a[k[i]]<a[l]) if (much(l,i)>=much(k[i],i)) l=k[i]; else { x=(much(k[i],i)-much(l,i))/(a[l]-a[k[i]])+i+1; if (x<=n&&(k[x]==0||a[k[i]]<a[k[x]])) k[x]=k[i]; } if (a[i]<a[l]) { f[i]=much(l,i)+b[i]; x=b[i]/(a[l]-a[i])+i+1; if (x<=n&&(k[x]==0||a[i]<a[k[x]])) k[x]=i; } } if (k[n]>0&&a[k[n]]<a[l]&&much(l,n)>much(k[n],n)) l=k[n]; printf("%lld",much(l,n)+b[n]); }方法②代码：
#include<cstdio> #include<iostream> using namespace std; int n,head,tail,mid,l,r,j; long long a[100000],b[100000],f[100000],k[100000],g[100000]; float xl(int x,int y) { return (g[x]-g[y])/(x-y); } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%lld",&a[i]); for (int i=1;i<=n;i++) scanf("%lld",&b[i]); head=1; tail=1; k[1]=n; f[n]=0; g[n]=f[n]+b[n]; for (int i=n-1;i>=1;i--) { if (head<tail) { l=head;r=tail; while (l<r-1) { mid=(l+r)/2; if (xl(k[mid+1],k[mid])<=-a[i]) r=mid; else l=mid; } if (xl(k[r],k[l])<=-a[i]) j=k[l]; else j=k[r]; } else j=k[head]; f[i]=g[j]+j*a[i]-i*a[i]; g[i]=f[i]+b[i]; if (head<tail) { while (xl(i,k[tail])>xl(k[tail],k[tail-1])) { tail--; if (tail==head) break; } } tail++; k[tail]=i; } printf("%lld",f[1]); }Description
有一个外星人控制了你的大脑。一开始你处于原点（0,0）。外星人有一个由(R,U,D,L)组成的长度为M 的操作序列，分别代表(右，上，下，左)。 平面上有N 个关键点，每当外星人给出一个操作，你需要在这个方向上找到最近的一个关键点，并走到那个点上。保证输入数据合法。 上图为第三个样例的图示。
Input
第一行两个整数N,M。 接下来N 行，每行两个整数xi,yi，代表第i 个点的坐标。 接下来一行，一个长度为M 的字符串，代表操作序列。
Output
一行两个整数，代表最终你所处的位置。
Sample Input
输入1： 4 4 1 1 1 0 0 1 0 0 RULD
输入2： 7 5 0 0 0 1 0 -1 1 0 1 -1 3 0 3 -1 DRRUD
输入3： 10 6 0 0 1 1 2 1 0 2 -1 2 -1 3 2 3 2 4 4 3 2 -1 ULURDL
Sample Output
输出1： 0 0
输出2： 3 -1
输出3： 1 1
Data Constraint
56%的数据，N≤3000，M≤3000。 100%的数据，N,M≤100000,xi,yi≤200000。
思路：二分+排序 先将坐标排序，一个数组存横坐标小到大排，一个数组存纵坐标小到大排 将每一个寻找，用二分实现
代码：
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; struct cf{int x,y;}a[100010],b[100010],tmp1,tmp2; bool cmp1(cf a,cf b){if (a.y<b.y||(a.y==b.y&&a.x<b.x)) return true; else return false;} bool cmp2(cf a,cf b){if (a.x<b.x||(a.x==b.x&&a.y<b.y)) return true; else return false;} int lx,ly,n,m; char c; int efl(cf s) { int l=1,r=n; while (l<r) { int mid=(l+r)>>1; if (b[mid].x<s.x||(b[mid].x==s.x&&b[mid].y<s.y)) l=mid+1; else r=mid; } return l; } int efh(cf s) { int l=1,r=n; while (l<r) { int mid=(l+r)>>1; if (a[mid].y<s.y||(a[mid].y==s.y&&a[mid].x<s.x)) l=mid+1; else r=mid; } return l; } int main() { freopen("tratincice.in","r",stdin); freopen("tratincice.out","w",stdout); scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) { scanf("%d%d",&lx,&ly); a[i].x=b[i].x=lx; a[i].y=b[i].y=ly; } sort(a+1,a+n+1,cmp1); sort(b+1,b+n+1,cmp2); for (int i=1;i<=m;i++) { while ((c=getchar())!='D'&&c!='R'&&c!='U'&&c!='L'); if (c=='U') { int w=efl(tmp2)+1; tmp1.x=b[w].x;tmp1.y=b[w].y; tmp2.x=b[w].x;tmp2.y=b[w].y; } if (c=='D') { int w=efl(tmp2)-1; tmp1.x=b[w].x;tmp1.y=b[w].y; tmp2.x=b[w].x;tmp2.y=b[w].y; } if (c=='L') { int w=efh(tmp1)-1; tmp1.x=a[w].x;tmp1.y=a[w].y; tmp2.x=a[w].x;tmp2.y=a[w].y; } if (c=='R') { int w=efh(tmp1)+1; tmp1.x=a[w].x;tmp1.y=a[w].y; tmp2.x=a[w].x;tmp2.y=a[w].y; } } printf("%d %d",tmp1.x,tmp1.y); }