工资
(money/money.in/money.out)
时限1000ms 内存256MB
聪哥在暑假参加了打零工的活动，这个活动分为n个工作日，每个工作日的工资为Vi。有m个结算工钱的时间,聪哥可以*安排这些时间，也就是说什么时候拿钱，老板说的不算，聪哥才有发言权！（因为聪哥是土豪，他是老板的老板）
聪哥不喜欢身上一次性有太多的钱，于是他想安排一下拿钱的时间，使他一次性拿的钱中最大的最小。（最后一天一定要领钱）
输入
第一行 2个数 n,m
接下来n行，每行一个数，代表Vi.
输出
最小的最大钱数。
样例输入
7 5
100
400
300
100
500
101
400
样例输出
500
样例说明
100 400//300 100//500//101//400//
“//”表示老大要去拿钱。
数据范围
20% 1<=n<=20
另 20% 1<=n<=50,Vi的和不超过1000
100% 1<=n<=100,000,m<=n,Vi<=10,000
第二题 藏妹子之处（excel）
问题描述：
今天CZY又找到了三个妹子，有着收藏爱好的他想要找三个地方将妹子们藏起来，将一片空地抽象成一个R行C列的表格，CZY要选出3个单元格。但要满足如下的两个条件：
（1）任意两个单元格都不在同一行。
（2）任意两个单元格都不在同一列。
选取格子存在一个花费，而这个花费是三个格子两两之间曼哈顿距离的和（如(x1,y1)和(x,y2)的曼哈顿距离为|x1-x2|+|y1-y2|）。狗狗想知道的是，花费在minT到maxT之间的方案数有多少。
答案模1000000007。所谓的两种不同方案是指：只要它选中的单元格有一个不同，就认为是不同的方案。
输入格式：
一行，4个整数，R、C、minT、maxT。3≤R,C≤4000, 1≤minT≤maxT≤20000。
对于30%的数据, 3 ≤ R, C ≤ 70。
输出格式:
一个整数，表示不同的选择方案数量模1000000007后的结果。
输入输出样例：
|
输入样例 |
3 3 1 20000 |
3 3 4 7 |
4 6 9 12 |
7 5 13 18 |
4000 4000 4000 14000 |
|
输出样例 |
6 |
0 |
264 |
1212 |
859690013 |
Problem 3 银河之星(galaxy.cpp/c/pas)
T1:
二分贪心
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define MAXN 100005
#define ll long long
using namespace std;
int a[MAXN];
int n,m;
int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if('-'==ch)f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int check(int w){
int cnt=,s=;
for(int i=;i<=n;i++){
if(s+a[i]>w){
cnt++;
if(cnt>m){
return ;
}
s=a[i];
}
else{
s+=a[i];
}
}
return ;
}
int main()
{
int L=,R=;
n=read();m=read();
for(int i=;i<=n;i++){
a[i]=read();
R+=a[i];
L=max(L,a[i]);
}
while(R-L>){
int mid=((ll)R+(ll)L)/;
if(check(mid)){
R=mid;
}
else{
L=mid+;
}
}
if(check(L)){
printf("%d\n",L);
}
else{
printf("%d\n",R);
}
return ;
}
Code1
T2:
数学分析,发现代价就是三个点组成的矩形的边长，枚举之后分两种情况：
1，两个点在矩形的对角线顶点，第三点到处逛~
左上-右下对角线 (x-1)*(y-1)
左下-右上对角线 (x-1)*(y-1)
2，一个点在矩形的一个顶点，其余两个点分别在其余的两条边
(x-1)(y-1)
然后矩形有4个顶点，所以是4*(x-1)(y-1)
可以证明，至少有一个点在矩形的顶点处
所以根据加法原理，有6*(x-1)(y-1)种情况，
然后矩形可以在局域里面到处跑，总共可以跑(n-x+1)*(m-y+1)处
乘起来即可
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define MOD 1000000007
#define ll long long
using namespace std;
ll n,m,s,t;
ll ans;
int main()
{
// freopen("data.in","r",stdin);
scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
n--;m--;
if(s%==) s++;
if(t%==) t--;
if(t>(n+m)*){
t=(n+m)*;
}
for(ll i=s;i<=t;i+=){
ll d=i/;
for(ll j=max(1LL,d-m);j<=min(n,d-);j++){
ans=(ans+(*(j-)*(d-j-))%MOD*(n-j+)%MOD*(m-(d-j)+)%MOD)%MOD;
}
}
printf("%lld\n",ans);
return ;
}
Code2
T3:
一开始以点的位置为状态，用hash加搜索，结果好慢好慢啊，T了8个点
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<queue>
#define MAXN 105
#define MOD 1000003
#define P 17
#define pii pair<int,int>
using namespace std;
int gx[]={,,,,,-,-,-};
int gy[]={,-,,,-,,,-};
int k,n,m,x0,y0;
bool b[MOD];
struct Node{
int s;
pii p[];
};
queue<Node> q;
int hash(Node t){
int ret=;
for(int i=;i<k;i++){
if(t.s&(<<i)){
ret=(ret+t.p[i].first*MAXN+t.p[i].second)%MOD;
}
ret=ret*P%MOD;
}
return ret;
}
int Abs(int x){
return (x>)?x:-x;
}
int bfs(){
while(!q.empty()){
int s=q.front().s;
pii p[];
memcpy(p,q.front().p,sizeof(p));
q.pop();
int L=,cnt;
for(int i=;i<k;i++){
if(s&(<<i)){
L++;
cnt=i;
}
}
if(==L){
if(Abs(p[cnt].first-x0)%==&&Abs(p[cnt].second-y0)%==){
return ;
}
continue;
}
int a[MAXN][MAXN]={};
for(int i=;i<k;i++){
if(s&(<<i)){
a[p[i].first][p[i].second]=i+;
}
}
for(int i=;i<k;i++){
if(s&(<<i)){
for(int d=;d<;d++){
int dx=p[i].first,dy=p[i].second;
for(int j=;j<=;j++){
dx+=gx[d];
dy+=gy[d];
}
if(<=dx&&dx<=n&&<=dy&&dy<=m&&!a[dx][dy]){
Node t;
t.s=s;
memcpy(t.p,p,sizeof(t.p));
t.p[i]=make_pair(dx,dy);
int h=hash(t);
if(!b[h]){
b[h]=;
q.push(t);
}
}
}
}
}
for(int i=;i<k;i++){
if(s&(<<i)){
for(int d=;d<;d++){
int dx=p[i].first,dy=p[i].second;
dx+=gx[d];
dy+=gy[d];
if(a[dx][dy]){
int v=a[dx][dy]-;
dx+=gx[d];
dy+=gy[d];
if(<=dx&&dx<=n&&<=dy&&dy<=m&&!a[dx][dy]){
Node t;
t.s=s^(<<v);
memcpy(t.p,p,sizeof(t.p));
t.p[i]=make_pair(dx,dy);
int h=hash(t);
if(!b[h]){
b[h]=;
q.push(t);
}
}
}
}
}
}
}
return ;
}
void solve(){
memset(b,,sizeof(b));
while(!q.empty()) q.pop();
Node t;
t.s=(<<k)-;
for(int i=;i<k;i++){
scanf("%d%d",&t.p[i].first,&t.p[i].second);
}
b[hash(t)]=;
q.push(t);
if(bfs()){
printf("Yes\n");
}
else{
printf("No\n");
}
}
int main()
{
// freopen("data.in","r",stdin);
while(~scanf("%d%d%d%d%d",&k,&n,&m,&x0,&y0)){
solve();
}
return ;
}
Code3-1
后来发现，应当抓住问题的性质，即能否到达，而不是最短距离之类
由于坐标相差3的倍数的点可以互相移动到达，不妨认为就是一个点了，然后只会存在9种点
0 1 2 0 1 2
3 4 5 3 4 5
6 7 8 6 7 8
0 1 2 0 1 2
3 4 5 3 4 5
6 7 8 6 7 8
这样移动三步的情况就解决了
然后移动两步比如0+4=8 3+4=5
注意需要考虑这种情况
1 X X
X X X
X X 1
一般来说0+8=4
但是这种情况下地图只有这么小，你的0跑到8底下就超出范围了
所以不能直接计算，需要枚举处理合法的情况
然后问题迎刃而解了
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<map>
#define MAXN 102
#define P 11
#define ll long long
using namespace std;
map<ll,bool> mp;
int gx[]={,,-,-,-,,,};
int gy[]={-,,-,,,-,,};
int K,n,m,ed;
int G[][];
ll hash(int a[]){
ll ret=;
for(int i=;i<;i++){
ret=ret*P+a[i];
}
return ret;
}
int place(int x,int y){
return ((x-)%)*+(y-)%;
}
void init(){
memset(G,-,sizeof(G));
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
for(int k=;k<;k++){
int x1=i+gx[k],y1=j+gy[k];
int x2=x1+gx[k],y2=y1+gy[k];
if(<=x2&&x2<=n&&<=y2&&y2<=m){
int t1=place(i,j);
int t2=place(x1,y1);
int t3=place(x2,y2);
G[place(i,j)][place(x1,y1)]=place(x2,y2);
}
}
}
}
}
int dfs(ll x){
if(x==ed){
return ;
}
int b[]={};
for(int i=;i>=;i--){
b[i]=x%;
x/=;
}
for(int i=;i<;i++){
for(int j=;j<;j++){
if(b[i]&&b[j]&&G[i][j]!=-){
int d[]={};
memcpy(d,b,sizeof(d));
d[i]--;
d[j]--;
d[G[i][j]]++;
ll h=hash(d);
if(!mp[h]){
mp[h]=;
if(dfs(h))
return ;
}
}
}
}
return ;
}
int main()
{
// freopen("data.in","r",stdin);
int x,y;
while(~scanf("%d%d%d%d%d",&K,&n,&m,&x,&y)){
mp.clear();
init();
int b[]={};
b[place(x,y)]++;
ed=hash(b);
b[place(x,y)]--;
for(int i=;i<=K;i++){
scanf("%d%d",&x,&y);
b[place(x,y)]++;
}
ll h=hash(b);
mp[h]=;
if(dfs(h)){
printf("Yes\n");
}
else{
printf("No\n");
}
}
return ;
}
Code3-2
这是一道搜索的好题，提醒我们铭记问题的性质决定求解的方法