线段和点
算法思想
贪心
代码程序
#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
bool vis[11000],dian[51000];
using namespace std;
int n,m;
struct s{
int l,r;
}str[11000];
bool cmp(s a,s b)
{
return ((a.l<b.l)||(a.l==b.l&&a.r<b.r));
}
int main()
{
mem(dian,false);
mem(vis,false);
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
int x;
scanf("%d",&x);
dian[x]=true;
}
for(int i=0;i<m;i++)
scanf("%d%d",&str[i].l,&str[i].r);
sort(str,str+m,cmp);
int ans=0,E;
for(int i=0;i<m;i++)
{
int mx=-INT_MAX;
if(!vis[i])
{
for(int j=str[i].l;j<=str[i].r;j++)
{
if(dian[j])
{
int tot=0;
for(int k=i+1;k<m;k++)
{
if(str[k].l<=j&&str[k].r>=j)
{
tot++;
}
else break;
}
if(tot>mx)
{
mx=tot;
E=j;
}
}
}
ans++;
for(int k=i+1;k<m;k++)
if(str[k].l<=E&&str[k].r>=E)
{
vis[k]=1;
}
else break;
}
}
printf("%d\n",ans?ans:-1);
return 0;
}
盾神与砝码称重
算法思想
dfs深搜+优化,先将砝码从小到大排序,并将用数组记录 由小到大的砝码的质量和,这样,一旦将要称的质量绝对值大于剩余质量,肯定不存在解了
代码程序
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int n,m;
int w[50],sum[50];
bool cmp(int a,int b)
{
return a>b;
}
bool dfs(int weight,int i)
{
if(weight==0)
{
return true;
}
if(abs(weight)>sum[i]) return false;
for(;i<n;i++)
{
if(dfs(weight+w[i],i+1)||dfs(weight-w[i],i+1))
return true;
}
return false;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>w[i];
sort(w,w+n,cmp);
sum[n]=0;
for(int i=n-1;i>=0;i--)
{
sum[i]=sum[i+1]+w[i];
}
for(int i=1;i<=m;i++)
{
int t;
cin>>t;
if(dfs(t,0)) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
开心的金明
算法思想
裸的01背包
代码程序
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n,m,v[30001],p[30001];
long dp[30001];
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
scanf("%d%d",&v[i],&p[i]);
}
for(int i=0;i<m;i++)
{
for(int j=n;j>=v[i];j--)
{
dp[j]=max(dp[j],dp[j-v[i]]+(v[i]*p[i]));
}
}
printf("%ld",dp[n]);
return 0;
}
剪格子
算法思想
裸的dfs
代码程序
#include <cstdio>
#define N 10
using namespace std;
int num[N][N];
int tag[N][N] = {0};
int m,n;
int r=100;
int bad(int i,int j)
{
if(i<0||i>=n||j>=m||j<0||tag[i][j]==1)
return 1;
return 0;
}
void go(int i,int j,int k,int count)
{
if(bad(i,j)||count < num[i][j])
return ;
k++;
if(count == num[i][j])
{
if(r>k)
r=k;
return ;
}
tag[i][j] = 1;
count -= num[i][j];
go(i - 1,j,k,count);
go(i + 1,j,k,count);
go(i,j + 1,k,count);
go(i,j - 1,k,count);
tag[i][j]=0;
}
int main()
{
int i,j;
int half = 0;
scanf("%d%d",&m,&n);
for(i = 0;i < n;i++)
for(j = 0;j < m;j++)
{
scanf("%d",&num[i][j]);
half += num[i][j];
}
if(half%2 == 0 && half >= num[0][0]*2)
{
half /= 2;
go(0,0,0,half);
}
if(r == 100)
r = 0;
printf("%d",r);
return 0;
}
九宫重排
算法思想
经典的八数码问题
代码程序
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct _Node
{
char tab[3][3];
int x,y;
int no;
}Node,*pNode;
int vx[4]={-1,1,0,0};
int vy[4]={0,0,-1,1};
Node res[400000];
int front=0,rear=0;
int vis[4000000],fact[9];
void input(pNode start);
void bfs(pNode start,pNode end);
void init_lookup_table();
int try_to_insert(int s);
int main()
{
Node start,end;
input(&start);
input(&end);
bfs(&start,&end);
printf("-1\n");
system("pause");
return 0;
}
void input(pNode start)
{
int i,j;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
scanf("%c",&( (start->tab)[i][j] ));
if((start->tab)[i][j]=='.')
{
start->x = i;
start->y = j;
}
}
}
start->no = 0;
getchar();
}
void bfs(pNode start,pNode end)
{
int i,j;
char ch;
pNode tmp;
init_lookup_table();
memcpy(&res[rear],start,sizeof(res[rear]));
try_to_insert(rear);
rear++;
while(front!=rear)
{
//printf("%d ",rear);
tmp = &res[front];
if(memcmp(tmp->tab,end->tab,sizeof(end->tab))==0)
{
printf("%d\n",tmp->no);
exit(0);
}
int no = tmp->no;
for(i=0;i<4;i++)
{
int xx = tmp->x+vx[i];
int yy = tmp->y+vy[i];
if(xx>=0 && xx<3 && yy>=0 && yy<3)
{
pNode p = &res[rear];
memcpy(p,tmp,sizeof(res[front]));
p->tab[tmp->x][tmp->y] = p->tab[xx][yy];
p->tab[xx][yy] = tmp->tab[tmp->x][tmp->y];
p->no = no+1;
p->x = xx;
p->y = yy;
if(try_to_insert(rear))
{
rear++;
}
}
}
front++;
//printf("%d ",rear);
}
}
void init_lookup_table()
{
int i;
fact[0] = 1;
for(i=1;i<9;i++)
{
fact[i] = fact[i-1]*i;
}
}
int try_to_insert(int s)
{
int i,j;
int code = 0;
for(i=0;i<9;i++)
{
int cnt = 0;
for(j=i+1;j<9;j++)
{
if(res[s].tab[j/3][j%3] < res[s].tab[i/3][i%3])
{
cnt++;
}
code += fact[8-i]*cnt;
}
}
if(vis[code])
{
return 0;
}
return vis[code] = 1;
}
快速幂
算法思想
积的取余等于取余的积的取余
代码程序
//#define LOCAL
#include <iostream>
#include <cmath>
#include <iostream>
using namespace std;
long long PowerMod(long long a, long long b, long long c)
{
long long ans = 1;
a = a % c;
while(b>0)
{
if(b % 2 == 1)
ans = (ans * a) % c;
b = b/2;
a = (a * a) % c;
}
return ans;
}
int main()
{
long long a,b,c;
cin>>a>>b>>c;
cout<<PowerMod(a,b,c);
return 0;
}