思维题

发表于2021-10-16更新于2021-10-19阅读次数

头脑风暴

Lights and Robot

点击查看思路 
  


推公式题，若没有D操作，答案为(R+C)*N-2*R*C;
有D操作，就是:(R+C)*N-2*R*C+(diag?1:0)*(N-2*C-2*R+4*D))



  

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
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
bitset<100010> Rmap,Cmap;
int R,C,D;
bool diag;
int N,M;
int T,E;

void initial(){
	R=C=D=0;
	diag=false;
	Rmap.reset();
	Cmap.reset();
}

bool blank(const char&x){
	return x==' '||x=='\n'||x==EOF;
}

int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&N,&M);
		initial();
		for(int i=0;i<M;i++){
			char op;
			while(blank(op=getchar()));
			if(op=='C'){
				scanf("%d",&E);
				if(Rmap[E]==true&&Cmap[E]==true){
					D--;
				}
				if(Cmap[E]==true){
					C--;
					Cmap[E]=false;
				}
				else{
					C++;
					Cmap[E]=true;
				}
				if(Rmap[E]==true&&Cmap[E]==true){
					D++;
				}
			}
			else if(op=='D'){
				diag=!diag;
			}
			else if(op=='R'){
				scanf("%d",&E);
				if(Rmap[E]==true&&Cmap[E]==true){
					D--;
				}
				if(Rmap[E]==true){
					R--;
					Rmap[E]=false;
				}
				else{
					R++;
					Rmap[E]=true;
				}
				if(Rmap[E]==true&&Cmap[E]==true){
					D++;
				}
			}
			// cout<<R<<' '<<C<<' '<<D<<' '<<N<<' '<<diag<<endl;
			printf("%lld\n",((ll)R+(ll)C)*(ll)N-(ll)2*(ll)R*(ll)C+(diag?(ll)1:(ll)0)*((ll)N-(ll)2*(ll)C-(ll)2*(ll)R+(ll)4*(ll)D));
		}
	}
}

Sequence I

点击查看思路 
  


取绝对值，其实就两种情况，要么a-b,要么b-a.那么每次分这两种情况暴力即可。


  

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
#include<bits/stdc++.h>

using namespace std;

int N,MAX,A[10],T;

int ABS(int x){
	if(x<0)return -x;
	return x;
}

void dfs(int ans,int d){
	if(d==N){
		if(ABS(ans)<MAX)MAX=ABS(ans);
		return;
	}
	dfs(ans+A[d],d+1);
	dfs(ans-A[d],d+1);
}

int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&N);
		MAX=1E8;
		for(int i=0;i<N;i++){
			scanf("%d",&A[i]);
		}
		dfs(0,0);
		printf("%d\n",MAX);
	}
}

Flight Collision

题意：一维坐标上飞机具有(x_i)坐标和速度(v_i)，其中速度是矢量
若两飞机相遇则会同时消失，问最后留下的飞机的编号

点击查看思路 
  


观察到性质每次相撞的飞机总是前一时间相邻的飞机
每次当前局面下第一次相撞的飞机是相对速度除以距离最大的飞机
每次删除这对飞机，然后添加 删除这对飞机之后相邻 的飞机。


  

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
#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef long double lb;
typedef pair<ll,ll> P;
const ll maxn=2e5+11;
ll v[maxn],x[maxn];
priority_queue<pair<lb,P>> q;
set<ll> s;
void add(ll i,ll j){
    if(v[i]-v[j]<=0)  return ;
    lb t=((lb)v[i]-(lb)v[j])/((lb)x[j]-(lb)x[i]);
    q.push({t,{i,j}});
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n;cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>x[i]>>v[i];
        s.insert(i);
    }
    for(ll i=1;i<n;i++){
        add(i,i+1);
    }
    while(!q.empty() && !s.empty()){
        P p=q.top().second;
        ll i=p.first,j=p.second;
        q.pop();
        if(!s.count(i) || !s.count(j))  continue;
        s.erase(i);s.erase(j);
        if(s.empty())  break;
        auto it=s.lower_bound(i);
        if(it==s.begin() || it==s.end())  continue;
        i=*(--it);
        it=s.lower_bound(j);
        j=*it;
        add(i,j);
    }
    cout<<s.size()<<endl;
    for(auto it=s.begin();it!=s.end();it++)  cout<<*it<<" ";
    return 0;
}

Stack Sort I

题意：有三个栈，a,b,c，初始a栈中有n < 1e3个元素，现需要借助b,c两个栈来操作使a栈中的元素按非递减排列。
操作是指将x栈顶的元素push到y栈顶。输出操作的过程，操作次数小于2e4。

点击查看思路 
  


递归，分治的思想
若能将一个非有序序列分为两个有序序列，那么这两个序列再归并就能形成一个有序序列。
故每次将一个序列分为两个序列，最后再将两个有序的序列归并即可。


  

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

/*
* @Author: Marhoosh
* @Date:   2021-07-22 10:27:41
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-10-17 21:44:32
*/
#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=2e5+11;
stack<ll> st[5];
vector<P> ans;
void opt(ll x,ll y){
    st[y].push(st[x].top());
    st[x].pop();
    ans.push_back({x+1,y+1});
}
void sort(ll x,ll n,ll d){
    if(n==1)  return ;
    ll m=n/2,k=n-m;
    ll y=(x+1)%3,z=(x+2)%3;
    for(ll i=1;i<=m;i++)  opt(x,y);
    for(ll i=1;i<=k;i++)  opt(x,z);
    sort(y,m,d^1);
    sort(z,k,d^1);
    for(ll i=0,j=0;i<m or j<k;){
        if(i==m)  opt(z,x),j++;
        else if(j==k)  opt(y,x),i++;
        else if(d ^ (st[y].top()<st[z].top()))  opt(z,x),j++;
        else  opt(y,x),i++;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll N;cin>>N;
    for(ll i=0,a;i<N;i++)  cin>>a,st[0].push(a);
    sort(0,N,0);
    cout<<ans.size()<<endl;
    for(auto i=ans.begin();i!=ans.end();i++)  cout<<(*i).first<<" "<<(*i).second<<endl;
    return 0;
}


Mine Sweeper II

题意：有A，B两个扫雷图，图的规格为n行m列，n,m < 1e3,让B最多操作n*m/2次，使得A，B两个数字之和相等。
操作是指将数字变雷，或雷变数字。

点击查看思路