这场比赛总的来讲不是很难，区分度并不高，第一题属于思维训练类型，第二题是一个比较新的DP题，第三题转化一下就是贪心+背包了
总的来说，要根据题目中的已知条件来判断出题人的意图，比如第一题给出的范围<=500摆明了就是有诈……
【联训赛10.16】丢钉子
Time Limit:20000MS Memory Limit:165536K
Total Submit:87 Accepted:42
Case Time Limit:1000MS
Description
学校里一年一度的自行车大赛又开始了！！可是ZL同学却非常不高兴，因为他不会骑自行车！所以他决定干扰这次比赛。他已经了解到了这次参加比赛的m名参赛选手的资料。他决定要进行一次惊天动地的干扰。
我们假设比赛场地是一个从起点处向右和向前无限延伸的跑道。编号为1到m的参赛队员从左到右并列排列。从比赛开始后的第1秒末，第2秒末，第3秒末，第4秒末……第m秒末他分别会投一枚钉子到当前排名第一的自行车的前面使其爆胎！（爆胎的自行车自动退出比赛，不再计入排名），当有多个人同时并列第一时，由于ZL童鞋在起点左侧的观众席，他总是丢在最接近左侧边缘的那个第一名参赛选手前（字典序最小的第一名）。
而参赛队员的资料只有两个，一个是他第一秒能前进的距离Vi，一个是他第一秒末后每秒秒能前进的距离Ai。
现在要你来求，每秒钟，ZL童鞋把钉子丢在了编号为几的参赛选手前。
Input
第一行为一个整数m，表示有m名参赛选手。
接下来有m行，分别表示编号为 i（从1到m）的参赛队员的数据，每行两个整数Vi，Ai。
Output
一行，m个整数，第i个数，表示第i秒退赛的选手的编号
Sample Input
样例1
3
100 1
100 2
3 100
样例2
5
1 1
2 2
3 3
4 1
3 4
Sample Output
样例1：
1 3 2
样例2：
4 5 3 2 1
Hint
【样例1说明】
第一组测试数据
第1秒
选手1前进到100米处。
选手2前进到100米处。
选手3前进到 3 米处。
此时选手1、2并列第一，ZL把钉子丢在1号选手前，1号选手退出比赛。
第2秒
选手2前进到102米处。
选手3前进到103米处。
此时选手3第一。ZL把钉子丢在3号选手前，3号选手退出比赛。
第3秒
选手2前进到104米处。
此时选手2第一。ZL把钉子丢在2号选手前，2号选手退出比赛。
1 <= m <= 50000
0 <= Vi <= 500
0 < Ai <= 100
Source
hdu4393
这题开始看起来毫无头绪，反正只要涉及到修改元素就是n^2的复杂度，因此不考虑对元素进行修改我们发现虽然m的范围很大，但是vi,ai的范围比较小，这就是此题的突破口
显然对于第0秒，两个人的距离最大为500，即一个人(A)在0处，另一个(B)在500处
这个时候如果B的速度大于A的速度，那么A肯定是追不上B的，显然此时排名不变
如果A的速度刚刚大于B的速度，即Va==Vb+1，那么A只需500秒就可以追上B
因此我们发现，不管选手的初始位置，速度如何分布，500秒之后的排名肯定就已经不变了
所以我们只需暴力模拟前500秒的情况，然后对500秒末进行排序处理就可以了
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=5e4+5,inf=0x3f3f3f3f,Mark=517;
inline void _read(int &x){
char t=getchar();bool sign=true;
while(t<'0'||t>'9')
{if(t=='-')sign=false;t=getchar();}
for(x=0;t>='0'&&t<='9';t=getchar())x=x*10+t-'0';
if(!sign)x=-x;
}
int n,s[maxn],d[maxn],tot;
bool vis[maxn];
struct wk{
int id,dist;
bool operator<(const wk& h)const{
return dist==h.dist?id<h.id:dist>h.dist;
}
}qust[maxn];
void solve1(){
int i,j;
for(i=0;i<n;i++){
int maxx=-inf,id;
for(j=1;j<=n;j++){
if(vis[j])continue;
s[j]+=i?d[j]:0;
if(maxx<s[j])maxx=s[j],id=j;
}
vis[id]=1;
printf("%d ",id);
}
}
void solve2(){
int i,j;
for(i=1;i<=Mark;i++){
int maxx=-inf,id;
for(j=1;j<=n;j++){
if(vis[j])continue;
if(maxx<s[j]+(i-1)*d[j])maxx=s[j]+(i-1)*d[j],id=j;
}
vis[id]=1;
printf("%d ",id);
if(i==n)break;
}
for(i=1;i<=n;i++){
if(vis[i])continue;
qust[++tot].dist=s[i]+(Mark+1)*d[i];
qust[tot].id=i;
}
sort(qust+1,qust+1+tot);
for(i=1;i<=tot;i++)printf("%d ",qust[i].id);
}
int main(){
_read(n);
for(int i=1;i<=n;i++){_read(s[i]);_read(d[i]);}
if(n<=2000)solve1();
else solve2();
}
【联训赛10.16】数字分配
Time Limit:20000MS Memory Limit:165536K
Total Submit:19 Accepted:14
Case Time Limit:1000MS
Description
有n个整数排成一行，编号1到n。现在给你A,B两个空盒子，需要你从这n个数中取出一些数，放入A，B两个盒子里。但要求A盒子里的数字的编号必须小于B盒子中数字的编号（也就是在原始序列中，A中所有数字均在B中数字的左侧），并且每个盒子里至少要有一个数字。
若将A盒子的所有数字进行XOR(异或)运算后的结果等于将B盒子的所有数字进行AND(与)运算的结果，我们认为这是一个“合理分配”。问，总共有多少种不同的“合理分配”方案？结果可能很大，mod 10^9+7再输出。
Input
第一行，一个整数n
第二行，n个空格间隔的整数，表示编号1到n的数字。
Output
一行，一个整数，表示所求的答案。
Sample Input
样例1：
3
1 2 3
样例2：
4
1 2 3 3
Sample Output
样例1：
1
样例2：
4
Hint
【样例1解释】
A:1 2 (1^2=3)
B:3
【样例2解释】
方案1：
A:1 2 (1^2=3)
B:3
方案2：
A:1 2
B:3
方案3：
A：1
B：2 3 （2&3=1）
方案4：
A: 1
B: 2 3
【数据范围】
n<=1000
0 <= 给出的数字 <1024
Source
hdu4901
将数列分为左右两部分，显然分界点是十分特殊的，因此我们用f[i][j]表示前i个数异或得到j的所有方案数(s[i]必选)g[i][j]表示第i~n个数与得到j的所有方案数(s[i]可能选)
这里f数组容易递推求得，但是g数组无法由其它状态转到现状态(不信可以试一试)，因此只能由现状态推到其他状态
最后计算ans就比较简单了(这里是没有重复的情况的，想一想为什么(提示：和所表示的状态有关))，详情见代码
#include<cstdio>
#include<iostream>
#define LL long long
using namespace std;
const LL maxn=1026,mod=1e9+7;
inline void _read(LL &x){
char t=getchar();bool sign=true;
while(t<'0'||t>'9')
{if(t=='-')sign=false;t=getchar();}
for(x=0;t>='0'&&t<='9';t=getchar())x=x*10+t-'0';
if(!sign)x=-x;
}
LL n,f[maxn][maxn],s[maxn],sum[maxn],ans,g[maxn][maxn];
int main(){
_read(n);
LL i,j;
for(i=1;i<=n;i++)_read(s[i]);
f[1][s[1]]=sum[s[1]]=g[n][s[n]]=1;
for(i=2;i<=n;i++){
for(j=0;j<=maxn;j++)f[i][j]=(sum[j^s[i]]+(j==s[i]))%mod;
for(j=0;j<maxn;j++)(sum[j]+=f[i][j])%=mod;
}
for(i=n-1;i;i--){
for(j=0;j<maxn;j++)(g[i][j&s[i]]+=g[i+1][j])%=mod,(g[i][j]+=g[i+1][j])%=mod;
g[i][s[i]]++;
}
for(j=0;j<maxn;j++)
for(i=1;i<n;i++)(ans+=f[i][j]*g[i+1][j]%mod)%=mod;
cout<<ans;
}
【联训赛10.16】盒子涂色
Time Limit:10000MS Memory Limit:165536K
Total Submit:6 Accepted:3
Case Time Limit:1000MS
Description
有n个盒子排成一行，编号1到n。一开始，所有的盒子都是黑色的。
有如下两种操作：
“1 ai xi”:你可以从编号1到ai间( [1,ai] )的黑盒子中任选xi个，将它们涂成白色；
“2 ai xi”:你可以从编号ai到n间( [ai,n] )的黑盒子中任选xi个，将它们涂成白色；
给出若干操作的序列，问最多能得到多少个白色的盒子？
得到最多的白色盒子最少需要使用多少个操作？
注意：
1.对于给出的操作，不一定要按给出的顺序执行。
2.每个操作，你都可以选择使用，也可以不使用它。
3.若一个操作对应的区间中没有足够的黑盒子，该操作将无法进行。
Input
第一行，两个整数n和m，表示有n个盒子，m个操作。
接下来m行，每行三个整数 si(1<=si<=2) , ai , xi (0 <= xi <= n,1<=ai<=n),
si代表操作的类型, ai和xi如题目描述。
Output
一行，两个空格间隔的整数，第一个表示最多能得到的白色盒子数，第二个表示最少所需的操作数。
Sample Input
样例1：
5 2
2 3 3
1 3 3
样例2：
10 6
2 10 2
2 9 3
1 5 4
2 5 1
1 6 2
2 8 0
Sample Output
样例1：
3 1
样例2：
7 3
Hint
【样例2解释】
采用了下列三个操作
1 5 4
2 5 1
1 6 2
操作1 5 4和1 6 2 将1到6全部涂成了白色
操作2 5 1 在7到10间任选一个涂成了白色
总共7个白色
【数据范围】
1 <= N <= 1000 ， 1<=M<=1000
Source
hdu4381
这道题的难点就在于盒子涂色是无序且混乱的，第一眼看根本无从下手我们可以尝试着让这个盒子变得有序，即贪心让盒子先涂满两边，再涂中间
这个贪心原则是显然正确的，运用贪心原则最后就是一个简单的背包，然后就搞定了
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1005,inf=0x3f3f3f3f;
int n,m,f1[maxn],f2[maxn],ans1=-inf,ans2=inf,cnt1,cnt2;
struct wk{int a,x;}Move1[maxn],Move2[maxn];
bool cmp1(wk a,wk b){return a.a==b.a?a.x>b.x:a.a<b.a;}
bool cmp2(wk a,wk b){return a.a==b.a?a.x>b.x:a.a>b.a;}
int main(){
int i,j,type;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d",&type);
if(type==1){
cnt1++;
scanf("%d%d",&Move1[cnt1].a,&Move1[cnt1].x);
}
else {
cnt2++;
scanf("%d%d",&Move2[cnt2].a,&Move2[cnt2].x);
}
}
sort(Move1+1,Move1+1+cnt1,cmp1);
sort(Move2+1,Move2+1+cnt2,cmp2);
memset(f1,inf,sizeof(f1));
memset(f2,inf,sizeof(f2));
f1[0]=f2[0]=f1[n+1]=f2[n+1]=0;
for(i=1;i<=cnt1;i++)
for(j=Move1[i].a;j>=Move1[i].x;j--)
f1[j]=min(f1[j],f1[j-Move1[i].x]+1);
for(i=1;i<=cnt2;i++)
for(j=Move2[i].a;j+Move2[i].x<=n+1;j++)
f2[j]=min(f2[j],f2[j+Move2[i].x]+1);
for(i=0;i<=n;i++)
for(j=i+1;j<=n+1;j++)
if(f1[i]<inf&&f2[j]<inf)ans1=max(ans1,i+n+1-j);
for(i=0;i<=ans1;i++)ans2=min(ans2,f1[i]+f2[n-ans1+i+1]);
printf("%d %d",ans1,ans2);
}
最后再说两句:
打开思维，一定要打开思维，平常的思维训练题一定要多听多看多想，一道题尝试用不同的方法解决！
(NOIP一周倒计时)