尺取法
POJ 2566: Bound Found
题解链接 https://www.cnblogs.com/smilesundream/p/5129758.html
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
题解链接 https://www.cnblogs.com/smilesundream/p/5129758.html
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
int n,k,t,a[maxn];
pii p[maxn];
int main() {
// ios::sync_with_stdio(false);
//freopen("Bound Found.in","r",stdin);
while(cin>>n>>k){
if(n==0&&k==0) break;
int sum=0;
p[0].first=0,p[0].second=0;
for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum+=a[i],p[i].first=sum,p[i].second=i;
sort(p,p+n+1);
while(k--){
cin>>t;
int l=0,r=1,ansl,ansr,ans,mi=INF;
sum=0;
while(r<=n&&mi){
sum=p[r].first-p[l].first;
if(abs(sum-t)<mi){
ans=sum;mi=abs(sum-t);ansl=p[l].second;ansr=p[r].second;
}
if(sum<t) r++;
else l++;
if(l==r) r++;
}
if(ansl>ansr) swap(ansl,ansr);
printf("%d %d %d\n",ans,ansl+1,ansr);
}
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ 2739: Sum of Consecutive Prime Numbers
题意；输入一个数字（<=1e5）求该数可由几种在素数表中连续的素数之和组成。
欧拉筛出所有素数，因为素数序列具有单调性，所以可以用尺取法。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
题意；输入一个数字（<=1e5）求该数可由几种在素数表中连续的素数之和组成。
欧拉筛出所有素数，因为素数序列具有单调性，所以可以用尺取法。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
int p[maxn],psum[maxn],v[maxn],m=0,n,ans;
void pre(int n){
for(int i=2;i<=n;i++){
if(!v[i]){
v[i]=i; //v[i]表示i最小的素因子
p[++m]=i;
}
for(int j=1;j<=m;j++){
if(p[j]*i>n||p[j]>v[i]) break;
v[p[j]*i]=i;
}
}
for(int i=1;i<=m;i++) psum[i]=psum[i-1]+p[i]; //psum[i]是p[i]的前缀和
}
int main() {
ios::sync_with_stdio(false);
//freopen("Sum of Consecutive Prime Numbers.in","r",stdin);
pre(maxn-5);
while(cin>>n){
if(!n) break;
int l=1,r=1,sum=0,ans=0;
while(r<=m&&p[r]<=n){ //素数序列具有单调性 所以可以用尺取法
sum=psum[r]-psum[l-1];
if(sum==n) ans++;
if(sum<n) r++;
else l++;
}
cout<<ans<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ 2100: Graveyard Design
正常尺取法即可。
后来看了题解，发现可以直接利用解方程。
三次方程求根公式很难，所以直接对n开三次方估算范围后验证。
PS：method_1结果为MLE，因为不能预处理前缀和。
同时使用vector会RE，原因未知。
method_2的结果为AC。
代码如下
/*
正常尺取法即可。
后来看了题解，发现可以直接利用1^2+2^2+...+k^2=k(k+1)(2k+1)/6=n解方程。
三次方程求根公式很难，所以直接对n开三次方估算范围后验证。
*/
#define method_2
#ifdef method_1
/*
MLE 数据量较大 不能预处理前缀和。
同时使用vector会RE，原因未知。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e7+5;
const int INF=0x3f3f3f3f;
ll n,sum[maxn],ans=0;
vector<pii>v;
int main() {
ios::sync_with_stdio(false);
//freopen("Graveyard Design.in","r",stdin);
cin>>n;
for(int i=1;i<=n;i++) sum[i]=i*i+sum[i-1];
ll l=1,r=1,res=0;
while(r*r<=n){
res=sum[r]-sum[l-1];
if(res==n){
ans++;
v.push_back(make_pair(r-l+1,l));
}
if(res<=n) r++;
else l++;
}
cout<<ans<<endl;
sort(v.begin(),v.end());
for(int i=v.size()-1;i>=0;i--){
cout<<v[i].first<<" ";
for(int j=v[i].second;j<=v[i].second+v[i].first-1;j++) cout<<j<<" ";
cout<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pii;
const int maxn=1e4+5;
const int INF=0x3f3f3f3f;
ll n,ans=0;
int p=0,a[maxn],b[maxn];
int main() {
ios::sync_with_stdio(false);
//freopen("Graveyard Design.in","r",stdin);
cin>>n;
ll l=1,r=0,res=0;
while(r*r<=n){
while(res<n){
r++;res+=r*r;
}
if(res==n){
ans++;
a[++p]=l;b[p]=r;
}
res-=l*l;
l++;
}
cout<<ans<<endl;
for(int i=1;i<=p;i++){
cout<<b[i]-a[i]+1;
for(int j=a[i];j<=b[i];j++) cout<<" "<<j;
cout<<endl;
}
return 0;
}
#endif
#ifdef method_3
/*
*/
#endif
反转
POJ 3185: The Water Bowls
一维的开关问题，枚举最左边的碗是否反转。后面所有的反转顺序就确定了。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
一维的开关问题，枚举最左边的碗是否反转。后面所有的反转顺序就确定了。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=20+5;
const int INF=0x3f3f3f3f;
int n=20,a[maxn],ans1=0,ans2=0,b[maxn];
void flip(int x,int a[]){
for(int i=x-1;i<=x+1;i++) a[i]=!a[i];
}
int main() {
ios::sync_with_stdio(false);
//freopen("The Water Bowls.in","r",stdin);
for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
for(int i=2;i<=n;i++){
if(a[i-1]){
flip(i,a);ans1++;
}
}
flip(1,b);ans2++;
for(int i=2;i<=n;i++){
if(b[i-1]){
flip(i,b);ans2++;
}
}
for(int i=1;i<=n;i++){
if(a[i]) ans1=INF;
if(b[i]) ans2=INF;
}
cout<<min(ans1,ans2);
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ 1222: EXTENDED LIGHTS OUT
经典的熄灯问题。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
经典的熄灯问题。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=5+5;
const int INF=0x3f3f3f3f;
const int dx[]= {-1,1,0,0,0};
const int dy[]= {0,0,1,-1,0};
int n,b[maxn][maxn],kase=0,c[maxn][maxn],ans1,res[maxn][maxn]= {0};
bool check(int x,int y) {
if(x<0||x>4||y<0||y>5) return false;
return true;
}
void click(int x,int y) {
for(int i=0; i<=4; i++) {
int newx=x+dx[i];
int newy=y+dy[i];
if(check(newx,newy)) {
b[newx][newy]^=1;
}
}
}
void solve() {
int ans=INF;
for(int i=0; i<=(1<<6)-1; i++) {
int cnt=0;
for(int j=0; j<=5; j++) {
if(i&(1<<j)) {
cnt++;
click(0,j);
}
}
for(int j=0; j<=3; j++) {
for(int k=0; k<=5; k++) {
if(!b[j][k]) {
cnt++;
click(j+1,k);
}
}
}
bool flag=true;
for(int j=0; j<=4; j++) {
for(int k=0; k<=5; k++) {
if(!b[j][k]) {
flag=false;
}
}
}
if(flag) {
if(cnt<ans) {
ans=cnt;
ans1=i;
}
}
for(int j=0; j<=4; j++) {
for(int k=0; k<=5; k++) {
b[j][k]=c[j][k];
}
}
}
}
void init(){
memset(res,0,sizeof(res));
ans1=0;
}
void show() {
for(int j=0; j<=5; j++) {
if(ans1&(1<<j)) {
res[0][j]=1;
click(0,j);
}
}
for(int j=0; j<=3; j++) {
for(int k=0; k<=5; k++) {
if(!b[j][k]) {
res[j+1][k]=1;
click(j+1,k);
}
}
}
for(int i=0; i<=4; i++) {
for(int j=0; j<=5; j++) {
cout<<res[i][j]<<" ";
}
cout<<endl;
}
}
int main() {
ios::sync_with_stdio(false);
//freopen("EXTENDED LIGHTS OUT.in","r",stdin);
cin>>n;
while(n--) {
init();
cout<<"PUZZLE #"<<++kase<<endl;
for(int i=0; i<=4; i++) {
for(int j=0; j<=5; j++) {
cin>>b[i][j];
b[i][j]=!b[i][j];
c[i][j]=b[i][j];
}
}
solve();
show();
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
弹性碰撞
POJ 2674: Linear world
第一问的解法和ant类似。
第二问需要用到一个性质，就是不管怎么碰撞，都会相对顺序都不变，而且开始有几个正向的，最后就会有几个正向的。
PS：如果将存储方式改为[1,n]就会WA，目前原因未知。
代码如下
/*
第一问的解法和ant类似。
第二问需要用到一个性质，就是不管怎么碰撞，都会相对顺序都不变，而且开始有几个正向的，最后就会有几个正向的。
PS：如果将存储方式改为[1,n]就会WA，目前原因未知。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=32000+5;
const int INF=0x3f3f3f3f;
struct node {
char p;
string name;
double pos;
} a[maxn];
double l,v;
int n;
double ans;
int ansp;
void init() {
ans=-1;
}
int main() {
// ios::sync_with_stdio(false);
//freopen("Linear world.in","r",stdin);
while(cin>>n) {
if(!n) break;
cin>>l>>v;
init();
for(int i=0; i<n; i++) cin>>a[i].p>>a[i].pos>>a[i].name; //pos自动按照升序排序 所以不用再排序
for(int i=0; i<n; i++) {
double dis;
if(a[i].p=='p'||a[i].p=='P') dis=l-a[i].pos;
else dis=a[i].pos;
if(dis>ans) {
ans=dis;
ansp=i;
}
}
//实现13位的保留两位小数
printf("%13.2lf ",(int)(ans/v*100)/100.0);
int sum=0;
// D(a[ansp].name);E;
if(a[ansp].p=='p'||a[ansp].p=='P') {
for(int i=ansp+1; i<n; i++) { //求ansp右边有多少个正向的
if(a[i].p=='p'||a[i].p=='P') sum++;
}
// D(sum);
cout<<a[n-1-sum].name<<endl;
} else {
for(int i=0; i<=ansp-1; i++) {
if(a[i].p=='n'||a[i].p=='N') sum++;
}
cout<<a[sum].name<<endl;
}
}
return 0;
}
折半枚举
POJ 3977: Subset
折半搜索即可。
PS：poj不支持long long的abs，要手动实现。
代码如下
/*
折半搜索即可。
PS：poj不支持long long的abs，要手动实现。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pii;
const int maxn=35+2;
const ll INF=0x3f3f3f3f3f3f3f3fll;
int n,cnt1,cnt2;
ll a[maxn],ans,ans1;
pii b[(1<<maxn/2+1)],c[(1<<maxn/2+1)];
void init(){
cnt1=cnt2=0;ans=ans1=INF;
}
ll ll_abs(ll x){
return x>=0?x:-x;
}
bool operator<(const pii i,const pii j){
//注意这里为了配合后面的lower_bound，对于first相同的pair，按照second降序排序，
//这样就能够在pos（pos=lower_bound返回值-数组首指针)的左右找到最小的子集
return i.first==j.first?i.second>j.second:i.first<j.first;
}
pii operator-(const pii i){
pii newi=i;newi.first=-newi.first;
return newi;
}
void dfs1(int x,ll sum,ll num){
if(x!=1){
b[++cnt1].first=sum;b[cnt1].second=num;
}
for(;x<=n/2+1;x++) dfs1(x+1,sum+a[x],num+1);
}
void dfs2(int x,ll sum,ll num){
if(x!=n/2+2){
c[++cnt2].first=sum;c[cnt2].second=num;
}
for(;x<=n;x++) dfs2(x+1,sum+a[x],num+1);
}
int main() {
ios::sync_with_stdio(false);
//freopen("Subset.in","r",stdin);
while(cin>>n){
if(!n) break;
// int d[]={0,1,2,2,4};
// D(lower_bound(d+1,d+5,3)-d);D(upper_bound(d+1,d+5,3)-d);E;
init();
for(int i=1;i<=n;i++) cin>>a[i];
dfs1(1,0,0);
sort(b+1,b+cnt1+1);
/*
for(int i=1;i<=cnt1;i++){
D(b[i].first);D(b[i].second);
E;
}
*/
for(int i=1;i<=cnt1;i++){ //元素只来自前一半
if(ll_abs(b[i].first)<ans){
ans=ll_abs(b[i].first);
ans1=b[i].second;
}
else if(ll_abs(b[i].first)==ans) ans1=min(ans1,b[i].second);
}
dfs2(n/2+2,0,0);
/*
for(int i=1;i<=cnt2;i++){
D(c[i].first);D(c[i].second);
E;
}
*/
for(int i=1;i<=cnt2;i++){ //元素只来自后一半
if(ll_abs(c[i].first)<ans){
ans=ll_abs(c[i].first);
ans1=c[i].second;
}
else if(ll_abs(c[i].first)==ans) ans1=min(ans1,c[i].second);
}
for(int i=1;i<=cnt2;i++){
int pos=lower_bound(b+1,b+cnt1+1,-c[i])-b-1;
// D(c[i]);D(b[pos]);E;
if(ll_abs(b[pos].first+c[i].first)<ans){
ans=ll_abs(b[pos].first+c[i].first);
ans1=c[i].second+b[pos].second;
}
else if(ll_abs(b[pos].first+c[i].first)==ans) ans1=min(ans1,c[i].second+b[pos].second);
if(pos+1<=cnt1){
if(ll_abs(b[pos+1].first+c[i].first)<ans){
ans=ll_abs(b[pos+1].first+c[i].first);
ans1=c[i].second+b[pos+1].second;
}
else if(ll_abs(b[pos+1].first+c[i].first)==ans) ans1=min(ans1,c[i].second+b[pos+1].second);
}
}
// D(cnt1);D(cnt2);E;
cout<<ans<<" "<<ans1<<endl;
}
return 0;
}
POJ 2549: Sumsets
枚举b+c和d-a，然后用二分查找判断。
时限很紧，method_1和method_2都TLE，只有method_3是500msAC。
代码如下
/*
*/
#define method_3
#ifdef method_1
/*
n^3暴力超时
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1000+5;
const int INF=0x3f3f3f3f;
int d,num[maxn],n;
map<int,int>mp;
void init(){
mp.clear();
}
int main() {
ios::sync_with_stdio(false);
//freopen("Sumsets.in","r",stdin);
while(cin>>n){
if(!n) break;
init();
for(int i=1;i<=n;i++) cin>>num[i],mp[num[i]]=1;
sort(num+1,num+n+1);
int flag=0;
for(d=n;d>=1;d--){
if(flag) break;
for(int i=1;i<=d;i++){
if(flag) break;
for(int j=i+1;j<=d;j++){
int k=num[d]-num[i]-num[j];
if(k==num[i]||k==num[j]) continue;
if(mp[k]==1){
cout<<num[d]<<endl;
flag=1;break;
}
}
}
}
if(d==0) cout<<"no solution"<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
折半枚举。
枚举b+c用map存储起来，然后逆序枚举d和a，然后在map判断是否存在d-a且a,b,c,d互不相同的情况。
但是当有大量数对键值相同时，map仍然后TLE。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1000+5;
const int INF=0x3f3f3f3f;
int d,num[maxn],n;
map<int,vector<pii> >mp; //注意这个map的对应形式
void init(){
mp.clear();
}
int main() {
// ios::sync_with_stdio(false);
//freopen("Sumsets.in","r",stdin);
while(cin>>n){
if(!n) break;
init();
for(int i=1;i<=n;i++) scanf("%d",&num[i]);
sort(num+1,num+n+1);
for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) mp[num[i]+num[j]].push_back(make_pair(num[i],num[j])); //枚举b+c
int flag=0;
for(d=n;d>=1;d--){
if(flag) break;
for(int i=1;i<=n;i++){ //枚举a 注意可能存在负数 所以num[d]不一定大于等于num[i] 所以枚举范围不是[1,d)
if(i==d) continue;
if(flag) break;
int now=num[d]-num[i];
for(int k=0;k<mp[now].size();k++){
if(mp[now][k].first!=num[i]&&mp[now][k].second!=num[i]&&mp[now][k].first!=num[d]&&mp[now][k].second!=num[d]){
cout<<num[d]<<endl;flag=1;break;
}
}
}
}
if(flag==0) cout<<"no solution"<<endl;
}
return 0;
}
#endif
#ifdef method_3
/*
枚举b+c和d-a，然后用二分查找判断。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1000+5;
const int INF=0x3f3f3f3f;
int num[maxn],n,tot1,tot2,ans;
struct node{
int v,l,r;
bool operator<(const node& h)const{return v<h.v;}
}a[maxn*maxn],b[maxn*maxn];
void init(){
tot1=0,tot2=0;ans=-INF;
}
bool check(node i,node j){
return (i.l!=j.l)&&(i.l!=j.r)&&(i.r!=j.l)&&(i.r!=j.r);
}
int main() {
// ios::sync_with_stdio(false);
//freopen("Sumsets.in","r",stdin);
while(cin>>n){
if(!n) break;
init();
for(int i=1;i<=n;i++) scanf("%d",&num[i]);
for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++){
a[++tot1].v=num[i]+num[j];a[tot1].l=i;a[tot1].r=j;
}
sort(a+1,a+tot1+1);
for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++){
b[++tot2].v=num[i]-num[j];b[tot2].l=i;b[tot2].r=j;
b[++tot2].v=num[j]-num[i];b[tot2].l=j;b[tot2].r=i;
}
for(int i=1;i<=tot2;i++){
int d=lower_bound(a+1,a+tot1+1,b[i])-a;
if(b[i].v==a[d].v&&check(b[i],a[d])){
ans=max(ans,a[d].v+num[b[i].r]);
}
}
if(ans==-INF) cout<<"no solution"<<endl;
else cout<<ans<<endl;
}
return 0;
}
#endif
