wspl09876

hyc

齐河一中蒟蒻一只

• 于  搜索, 暴力  阅读 

搜索专题

会场预约
找一个最小的r加进集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>  
#include <algorithm> 
#include<iostream> 
#define maxn 1000000    
#include<set>
using namespace std;
int n;
struct node{
    int s,t;
    bool operator<(const node &v)const{
        if(t==v.t)
            return s<v.s;
        return t<v.t;
    }
};
set <node> c; 
int main()
{
	scanf("%d",&n); set<node>::iterator w;
	for(int i=1;i<=n;i++)
	{
		char b;int s,t;
		cin>>b;
		if(b=='A')
		{
			scanf("%d%d",&s,&t);
			int cnt=0;
			while(1){
				 w=c.lower_bound((node){0,s});
				if(w!=c.end()&&t>=w->s)
				{
					c.erase(w);
					cnt++;
					continue;
				}
				c.insert((node){s,t});
			break;
			}
			printf("%d\n",cnt);
			
		}
		else printf("%d\n",c.size());
	}
	
	
}

油滴扩展
这个题很恶心啊。。
精度处理太tm恶心了。。。。。。。。。。。
思路：
因为n<=6，这也太小了
直接求出全排列来，求出所有点之间的距离，这个点扩展的距离就等于到已确定的点的距离-它的半径的最小值，然后一点点模拟。。
距离小于之前的半径了，就把他的半径付为零，我因这wa曾了四个点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const double p=3.1415926535;
double xx,x2,yy,y2,x[19999],y[19999];
bool ff[3000];
int n;
double w[199999],f[1999][1999],minn=9999999999;
int b[199999];
double jl(double x,double y,double z,double w){
    double xxx=x-z;
    double yyy=y-w; 
    return (double)sqrt(xxx*xxx+yyy*yyy);
}
double min(double x,double y)
{
    return x<y?x:y;
}
double abs2(double x)
{
    return x>=0?x:-x;
}
void dfs(int ww){
    if(ww==n+1)
    {
        memset(w,127,sizeof(w));
        for(int i=1;i<=n;i++)
        {
             w[b[i]]=min(abs2(x[b[i]]-(double)x2),abs2((double)xx-x[b[i]]));
            w[b[i]]=min(abs2(y[b[i]]-(double)y2),w[b[i]]);w[b[i]]=min(abs2((double)yy-y[b[i]]),w[b[i]]);
            for(int j=1;j<i;j++)
            {
                
                w[b[i]]=min(w[b[i]],f[b[i]][b[j]]-w[b[j]]);
				if(w[b[i]]<0)w[b[i]]=0;
            }
        }
        
        double www=(double)abs(xx-x2)*abs(yy-y2);
        for(int i=1;i<=n;i++)
        {
            //printf("%lf ",w[b[i]]);
            www-=w[b[i]]*w[b[i]]*p;
        } 
        minn=min(minn,www);
        return ;
    }
    for(int i=1;i<=n;i++)
    {
        if(!ff[i])
        {
            b[ww]=i;
            ff[i]=1;
            dfs(ww+1);
            ff[i]=0;
            
        }
    }
}
int main()
{
    

    scanf("%d",&n);

    scanf("%lf%lf%lf%lf",&x2,&y2,&xx,&yy);
    for(int i=1;i<=n;i++)
    scanf("%lf%lf",&x[i],&y[i]);
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
     {
         if(i!=j)
         {
             f[i][j]=jl(x[i],y[i],x[j],y[j]);
         
         }
     }
     
    dfs(1);
    printf("%d",int(minn+0.5));
     return 0;
}

引水入城
疯狂爆搜233333
dfsdfs%%%%
许多大佬都用bfs判断，这里我用了dfs，就不用再写bfs了。
思路
这里写图片描述
很容易发现区间一定是连续的，否则不行，就可以先爆搜出区间左和右，转化为一个区间覆盖问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,ans;
struct st{
    int l,r;
}s[1999];
int cmp(const st &a,const st &b)
{
    if(a.l<b.l||a.l==b.r&&a.r<b.r)return 1;
    return 0;
}
int a[1999][1999],f[1999][1999],q[1999][1999],ff[19999];
int xx[4]={1,-1,0,0},yy[4]={0,0,1,-1},maxn=0;
int dfs(int w,int x,int y)
{
    if(x==n)
    {
        
        s[w].l=min(s[w].l,y);s[w].r=max(s[w].r,y);
    }
    for(int i=0;i<=2;i++)
    {
        int xxx=x+xx[i];
        int yyy=y+yy[i];
        if(xxx<1||xxx>n||yyy<1||yyy>m) continue;
        if(a[xxx][yyy]<a[x][y]&&!q[xxx][yyy])
        {
            q[xxx][yyy]=1;
            dfs(w,xxx,yyy);
        }
    }
}


int main()
{
    scanf("%d%d",&n,&m);
   
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
     scanf("%d",&a[i][j]);
    for(int i=1;i<=m;i++)
    if(a[1][i]>=a[1][i-1]&&a[1][i]>=a[1][i+1])
    {
        q[1][i]=1;
        dfs(i,1,i);
    }
    
    for(int i=1;i<=m;i++)
    if(!q[n][i]) ans++;
    if(ans) {
        printf("0\n%d",ans);
        return 0;
    }
    else {
	for(int i=1;i<=m;i++)
    s[i].l=999999999,s[i].r=0;
    for(int i=1;i<=m;i++)
    if(a[1][i]>=a[1][i-1]&&a[1][i]>=a[1][i+1])
    {
    	memset(q,0,sizeof(q));
        q[1][i]=1;
        dfs(i,1,i);
    }
    	
    	
        sort(s+1,s+m+1,cmp);
        int i=m;while(s[i].l==999999999)i--;
        
        int tot=0;
    
        while(maxn<m){
            int wwww=maxn;
            for(int j=1;j<=i;j++){
            if(s[j].l<=maxn+1)
            wwww=max(s[j].r,wwww);
            }
            tot++;
            maxn=wwww;
        }
        printf("1\n%d",tot);
    }
    
}

小木棍
爆搜，我觉得我的应该更优，可不行，不知为什么，就看了题解
加了剪枝
1.如果不行，比他大的也不行。
2.如果第一个不行剩下的都不行
3.相同的不行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<cstdio>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
int cmp(const int a,const int b)
{
    return a>b;
}
int n,s,x[1999],vis[1999],maxn,ans,i,tot;
int dfs(int w,int q,int p){

    if(p==tot)
    {
        return 1;
    }
    if(w==0)
    {
    if(dfs(i,1,p+1)) return 1;    ; 
    }
    
    for(int j=q;j<=n;j++)
    {
        if(!vis[j]&&x[j]<=w)
        {
            vis[j]=1;
             if(dfs(w-x[j],j+1,p))return 1;
            vis[j]=0;
            if(w==x[j]||w==i) break;
            while(x[j+1]==x[j])j++;
            }
    }
    return 0;
}
int main()
{
    scanf("%d",&n);
    for(int j=1;j<=n;j++)
    {
        scanf("%d",&x[j]);
        if(x[j]<=50)
        {
        maxn=max(maxn,x[j]);
        s+=x[j];    
        }
        else n--,j--;
    }
    sort(x+1,x+n+1,cmp);

    for(i=maxn;i<=s;i++)
    if(s%i==0)
    {
        
         tot=s/i;
        if(dfs(i,1,0))
        {
        printf("%d",i);
        return 0;
        }
    }

}

八数码难题
调了一下午终于ac了，恶心死我了23333333
这个题大佬们都是用什么康托展开，什么hash。。。
作为一个懒。。我不想写了，就写了个bool，暴力判断重的情况
可是九维的bool会爆数组啊，那我们就要想一个问题，因为数码不会重，知道了前八位，最后一位可以推出来，这样就不会爆了，就可以尽情的去爆搜了
我用了一个bfs
思路：先取出一个0，从0开时搜，交换值
交换值时打一个表就很好解决了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<cstdio>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
using namespace std;
struct st{
	int s;
	int l;
	int ans;
};
bool ss[88888888];int n;
int mb=123804765;
int p[9]={100000000,10000000,1000000,100000,10000,1000,100,10,1};
int xx[9]={-1,3,-3,1};
	queue <st> q;
int bfs(){

	ss[n/10]=1;
	
	while(!q.empty())
	{
		st x = q.front();
		if(x.s == mb) {
			printf("%d",x.ans);
			return 1;
		}
		q.pop();
		for(int i=0;i<=3;i++)
		{
			
			
				int x2=x.l+xx[i];
				int j=x.l;
				if(x2<0||x2>8) continue; 
				if(j%3==2&&xx[i]==1) continue;
				if(j%3==0&&xx[i]==-1) continue;
					
					int w=(x.s/p[x2])%10;
					int www=(x.s/p[j]+w)*p[j]+x.s%p[j];
					www=www/p[x2]/10*10*p[x2]+www%p[x2];
					if(!ss[www/10])
					{
					//	printf("%d %d\n",www,x.ans+1);
						ss[www/10]=1;
						st o;o.s=www;o.l=x2;o.ans=x.ans+1;
						q.push(o);
					}
				
				
			
			
		}
	}
} 
int main()
{
	
	scanf("%d",&n);
	int ww=n,t=8;
	
	while(ww){
		if(ww%10==0)
		break;
		t--;
		ww/=10;
	}
	st o;
	o.s=n; o.l=t;o.ans=0;
	q.push(o);
	bfs();
	return 0;
}

虫食算
这个题很6啊
字符串处理很恶心啊，在我调了两个晚自习之后终于a了
思路：枚举每一个数字代表哪一个字母，如果是30分，就是一个全排列啊，找出所有排列前情况，暴力判断是否过
而这样显然，26的阶乘会炸的很惨，所以我们就需要很多优化
1.如果一竖行的都算出来了，直接判断是否正确，就不用枚举下面的了
2.如果第一位的加起来大于等于n了，就要进位了，这是不符合题意的
3.按从后往前的的顺序搜，先枚举最后的，一排一排的枚举，找出一个序列，这样可以使1优化和更优

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<stdlib.h>
using namespace std;
int n,ff[999];
int z[999], b[399];char w[399];
char a[399],c[399];int pos[999],cnt,s[999]; 
int add()
{
    memset(z,0,sizeof(z));
    
    for(int i=n-1;i>=0;i--)
    {
        z[i]+=b[a[i]-'A']+b[c[i]-'A'];
        z[i-1]+=z[i]/n;
        z[i]%=n;
        
    }
    
    for(int i=0;i<n;i++)
    if(z[i]!=b[w[i]-'A']) return 0;
    return 1;
}
bool check1()
{
    for(int i=n-1;i>=0;i--)
     if(b[a[i]-'A']!=-1&&b[c[i]-'A']!=-1&&b[w[i]-'A']!=-1)
      if(((b[a[i]-'A']+b[c[i]-'A'])%n!=b[w[i]-'A'])&&((b[a[i]-'A']+b[c[i]-'A']+1)%n!=b[w[i]-'A']))
       return 0;
     return 1;
}
void dfs(int ww){
	if(b[a[0]-'A']+b[c[0]-'A']>n-1)return ;
	if(!check1())return ;
    if(ww==n)
    {
        if(add())
        {
        for(int i=0;i<n;i++)
        printf("%d ",b[i]);
        
        exit(0);
        }
        return ;
    }
    for(int i=n-1;i>=0;i--)
    {
        if(!ff[i])
        {
        	b[pos[ww]]=i;
            ff[i]=1;
            dfs(ww+1);
            ff[i]=0;
            b[pos[ww]]=-1;
        }
    }
}
int main()
{
    

    scanf("%d",&n);
    for(int i=0;i<=n;i++) b[i]=-1;
    for(int i=0;i<n;i++)cin>>a[i];    for(int i=0;i<n;i++)cin>>c[i];    for(int i=0;i<n;i++)cin>>w[i];
	for(int i=n-1;i>=0;i--){
		if(!s[a[i]-'A'])
		{
			pos[cnt++]=a[i]-'A';
			s[a[i]-'A']=1;
		}
		if(!s[c[i]-'A'])
		{
			pos[cnt++]=c[i]-'A';
			s[c[i]-'A']=1;
		}
		if(!s[w[i]-'A'])
		{
			pos[cnt++]=w[i]-'A';
			s[w[i]-'A']=1;
		}

		if(cnt==n)break;
	}
    dfs(0);
     return 0;
}

mayan游戏
这个题是个大爆搜。。。
考虑把一个位置的方块移到右面，就等同于把一个方块移到左面，所以只枚举向右的就行了，可以保证优先级，但这个位置的方块如果是空的，虽然是向右移的，但题目不让这么输出，所以打个标记就行了。
所以我们的思路就出来了，先枚举换的位置，如果相同就不用换，然后交换，清除，使空中的快下降，
下降完后一次次清除，一次次下降，直到不行为止，这样的话不会超时吗，因为n只有5啊，所以不会爆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<stdlib.h>
using namespace std;
int a[9][9],n;
struct st{
    int x,y,f;
}ans[19];
int empty(){//检查是否为空
    for(int i=0;i<5;i++)
        for(int j=0;j<7;j++)
        if(a[i][j])return 0;
        return 1;
}
int check()//检查有没有小于三的块
{
    int sum[12];
    memset(sum,0,sizeof sum);
    for(int i=0;i<5;i++)
        for(int j=0;j<7;j++)
            sum[a[i][j]]++;
    for(int i=1;i<=10;i++)
        if(sum[i]!=0&&sum[i]<3) return 0;
        return 1;
}
void drop(){//使上面的下降
    int num[10][10];  
    memset(num,-1,sizeof num);  
    for(int i=0;i<5;i++)
    {  
        int h=0;  
        for(int j=0;j<7;j++)  
            if(a[i][j])  
                num[i][h++]=j;  
    }  
    for(int i=0;i<5;i++)  
        for(int j=0;j<7;j++)  
            a[i][j]=num[i][j]==-1?0:a[i][num[i][j]];  
      return ;
}
int clear(){//消除
    int flag=0;
    for(int i=0;i<=2;i++)
    for(int j=0;j<7;j++)
    {
        if(a[i][j])
        {
            int x=i+1;
            while(a[i][j]==a[x][j]&&x<5) x++;x--;
            if(x-i>=2)
            {
                for(int k=i;k<=x;k++)
                {
                    int yu=j+1,yd=j-1;
                    while(a[i][j]==a[k][yu]&&yu<7)yu++;yu--;
                    while(a[i][j]==a[k][yd]&&yd>=0)yd--;yd++;
                    if(yu-yd>=2){
                        for(int q=yd;q<=yu;q++)
                        a[k][q]=0;
                    }
                }
                for(int k=i;k<=x;k++)
                a[k][j]=0;
                flag=1;
            }
            
        } 
    }
    for(int i=0;i<5;i++)
    for(int j=0;j<=4;j++)
    {
        if(a[i][j])
        {
            int y=j+1;
            while(a[i][j]==a[i][y]&&y<7) y++;y--;
            if(y-j>=2)
            {
                for(int k=j;k<=y;k++)
                {
                    int xu=i+1,xd=i-1;
                    while(a[i][j]==a[xu][k]&&xu<5)xu++;xu--;
                    while(a[i][j]==a[xd][k]&&xd>=0)xd--;xd++;
                    if(xu-xd>=2){
                        for(int q=xd;q<=xu;q++)
                        a[q][k]=0;
                    }
                }
                for(int k=j;k<=y;k++)
                a[i][k]=0;
                flag=1;
            }
            
        } 
    }
    if(flag) return 1;
    else return 0;
}
void dfs(int X){
    if(X>=n+1)
    {
        if(empty()){
            for(int i=1;i<=n;i++){
                if(ans[i].f)
                printf("%d %d %d\n",ans[i].x,ans[i].y,1);
                else
                printf("%d %d %d\n",ans[i].x+1,ans[i].y,-1);
                
            } exit(0);
        }
        return ;
    }
    if(!check())return ;
    for(int i=0;i<4;i++)
    for(int j=0;j<7;j++)
    {
        if(a[i][j]!=a[i+1][j])
        {
            ans[X].x=i;//记录交换的坐标和标记
            ans[X].y=j;
            ans[X].f=a[i][j];
            int tmp[6][8];
            memcpy(tmp,a,sizeof tmp);  
            swap(a[i][j],a[i+1][j]);  
            drop();  
            while(clear()) drop();
            dfs(X+1); 
            ans[X].x=0;  
            ans[X].y=0;  
            ans[X].f=0;  
            memcpy(a,tmp,sizeof a);  
        }
    }
}
int main()
{
    scanf("%d",&n);
    
    for(int i=0;i<5;i++)
    {
        int x=1,t=0;
        while(x!=0)
        {
            scanf("%d",&x);
            a[i][t++]=x;
        }
    }

    dfs(1);
    printf("-1");
}
最近的文章

dp专题

互不侵犯的king状压dp题每一行放不放国王可以用1010010来表示所以每一行的状态可以看成一个二进制数这样n是小于9的，可以把小于2^n，（因为2^9是512，很小）的数打表存出来把自己和自己冲突的筛掉，然后记下有多少1，判断他们是否冲突。预处理完了，接下来是dp了动态转移方程：dp[i][q+ …

• 于  dp 继续阅读
更早的文章

模拟水题

…

• 于 继续阅读