F. Robot on the Board 2（搜索）
题意：
题意：有一个n*m的棋盘，每个格子上有一个字符，U, D, L, R四个之一。机器人从任意一个格子为起始位置，按着字符方向（U,D,L,R分别是上下左右）走一格，直到碰到走过的格子或者出边界，最长的运动路径长度是多少。输出使运动路径最长的起始位置和路径长度
题解：
遍历每个点并对每个点按照规则搜索，同时记录走过的路径，走过的路径无需重复搜索。同时要注意如果搜索的路径有环，那么要把有环的地方的$len[x][y]$标记为同样的大小。每个点都只会最多被访问两次，复杂度O(n*m)。
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
|
#include<bits/stdc++.h>
#define pii pair<int,int>
#define pdd pair<double,double>
using namespace std;
typedef long long ll;
const int MAXN = 1e6+10;
const int INF = 0x3f3f3f3f;
const ll MOD = 998244353;
int n,m;
char a[2000+2][2000+2];
int len[2000+2][2000+2];
int vis[2000+2][2000+2];
vector<pii>t;
bool is_cir = false;
bool check(int x,int y)
{
if(vis[x][y]==1) {is_cir=true;return false;}
if(vis[x][y]==1||x<=0||y<=0||x>n||y>m) return false;
else return true;
}
void dfs(int x,int y)
{
is_cir = false;
t.clear();
while(check(x,y))
{
t.push_back({x,y});
vis[x][y] = 1;
if(a[x][y]=='U') x--;
else if(a[x][y]=='D') x++;
else if(a[x][y]=='L') y--;
else if(a[x][y]=='R') y++;
}
int xx=x, yy=y;
int cnt = len[x][y];
for(int i=t.size()-1;i>=0;i--)
{
cnt++;
len[t[i].first][t[i].second] = cnt;
if(is_cir&&t[i].first==xx&&t[i].second==yy)
{
for(int j=i;j<t.size();j++) len[t[j].first][t[j].second] = cnt;
is_cir = false;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
cin>>n>>m;
for(int i=0;i<=n+2;i++)
{
for(int j=0;j<=m+2;j++)
{
len[i][j] = 0;
vis[i][j] = 0;
}
}
for(int i=1;i<=n;i++)
{
string s;
cin>>s;
for(int j=1;j<=m;j++)
{
a[i][j] = s[j-1];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
dfs(i,j);
}
}
int maxx = -1;
pii ans;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(len[i][j]>maxx)
{
maxx = len[i][j];
ans.first = i;
ans.second = j;
}
}
}
cout<<ans.first<<" "<<ans.second<<" "<<maxx<<endl;
}
return 0;
}
|
G. Banquet Preparations 1(构造，贪心)
题意：
给n组数，每组包含$ai,b_i$两个数，现在可以对每组数做减去操作，操作是：使a减去一个非负数x，使b减去一个非负数y，同时保证x+y=m。希望每个数操作后使得$|\Sigma{i=1}^nai-\Sigma{i=1}^nb_i|$最小，输出每组数的a和b分别多少。
题解：
一开始的这些数总共大小是$\Sigma{i=1}^na_i+\Sigma{i=1}^nbi$，需要减去的大小是$n*m$,那么操作完后这些数的总共大小是$left = \Sigma{i=1}^nai+\Sigma{i=1}^nb_i-n*m$, 我们希望剩下得$a，b$绝对值差最小，即进行完减去操作后，a和b两边的和各是$left/2$。
我们可以求出$a_i$进行完减去操作后的范围$[l,r]$, 只需要构造出$a_i$的和尽量接近$left/2$即可。
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
| #include<bits/stdc++.h>
#define pii pair<int,int>
#define pdd pair<double,double>
using namespace std;
typedef long long ll;
const int MAXN = 1e6+10;
const int INF = 0x3f3f3f3f;
const ll MOD = 998244353;
pii a[MAXN];
pii rg[MAXN];
int ler[MAXN];
pii ori[MAXN];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>n>>m;
ll sum = 0;
for(int i=1;i<=n;i++)
{
cin>>a[i].first>>a[i].second;
ori[i].first = a[i].first;
ori[i].second = a[i].second;
sum += 1ll*a[i].first + 1ll*a[i].second;
ll l = max(0,m-a[i].second);
ll r = min(m,a[i].first);
rg[i].first = a[i].first - r;
rg[i].second = a[i].first - l;
}
sum = sum - 1ll*n*m;
sum/=2;
ll lef = sum;
for(int i=1;i<=n;i++)
{
lef-=rg[i].first;
}
if(lef>0)
{
for(int i=1;i<=n;i++)
{
a[i].first -= rg[i].first;
ler[i] = rg[i].second - rg[i].first;
}
for(int i=1;i<=n;i++)
{
if(lef>=ler[i])
{
a[i].first -= ler[i];
lef -= ler[i];
}
else
{
a[i].first -= lef;
lef-=lef;
}
}
ll ans = 0;
for(int i=1;i<=n;i++)
{
ans+=1ll*(ori[i].first-a[i].first)-1ll*(ori[i].second-(m-a[i].first));
}
cout<<abs(ans)<<endl;
for(int i=1;i<=n;i++)
{
cout<<a[i].first<<" "<<m-a[i].first<<endl;
}
}
else
{
ll ans = 0;
for(int i=1;i<=n;i++)
{
a[i].first -= rg[i].first;
a[i].second =m - a[i].first;
ans+=1ll*(ori[i].first-a[i].first)-1ll*(ori[i].second-a[i].second);
}
cout<<abs(ans)<<endl;
for(int i=1;i<=n;i++)
{
cout<<a[i].first<<" "<<a[i].second<<endl;
}
}
}
return 0;
}
|
H. Banquet Preparations 2(双指针，区间合并)
题意：
$n$个非负三元组$a_i, b_i, m_i$，保证$a_i + b_i ≥ m_i$ 。让每个三元组$a_i$ , $b_i$总共减少$m_i$。问最后使得减少后的$(a_i,b_i)$对 不同的对数最少的方案，和对数。
题解：
当一组数做完减去操作后，他们剩下的和是$sum=a_i+b_i-m_i$，只要当剩下的和$sum$相同才有可能$a，b$分别相同，所以我们先按照$sum$作为第一关键字进行排序。
接下来我们求出每个$a$的范围，如果剩下的$sum$相同且$a$的范围有交集，那么两组数就可以使得$(a,b)$相同。然后我们把a的范围$[range_l,range_r]$的$range_l$作为第二关键字，$range_r$作为第三关键字，最后对他们用双指针做区间合并，如果无交集区间则ans++统计答案。排序复杂度$O(nlogn)$，双指针区间合并$O(n)$，总复杂度$O(nlogn)$。
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
|
#include<bits/stdc++.h>
#define pii pair<int,int>
#define pdd pair<double,double>
using namespace std;
typedef long long ll;
const int MAXN = 1e6+10;
const int INF = 0x3f3f3f3f;
const ll MOD = 998244353;
struct node{
int a,b,m;
int sum=0;
int rgl,rgr;
int newa,newb;
int id;
}p[MAXN];
bool cmp(node a,node b)
{
if(a.sum==b.sum)
{
if(a.rgl==b.rgl) return a.rgr<b.rgr;
else return a.rgl<b.rgl;
}
else return a.sum<b.sum;
}
bool cmp2(node a,node b)
{
return a.id<b.id;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>p[i].a>>p[i].b>>p[i].m;
p[i].id = i;
p[i].rgl = max(0,p[i].a-p[i].m);
p[i].rgr = min(p[i].a,p[i].a-(p[i].m-p[i].b));
p[i].sum = p[i].a + p[i].b - p[i].m;
}
sort(p+1,p+1+n,cmp);
int ans = 0;
int l = p[1].rgl,r = p[1].rgr;
int last_i = 1;
for(int i=2;i<=n;i++)
{
if(p[i].sum==p[i-1].sum)
{
int nowl = p[i].rgl, nowr = p[i].rgr;
if(nowl<=r)
{
l = nowl;
r = min(r,nowr);
}
else
{
for(int j=last_i;j<=i-1;j++)
{
p[j].newa = l;
p[j].newb = p[j].b - (p[j].m-(p[j].a-l));
}
ans++;
l = p[i].rgl;
r = p[i].rgr;
last_i = i;
}
}
else
{
for(int j=last_i;j<=i-1;j++)
{
p[j].newa = l;
p[j].newb = p[j].b - (p[j].m-(p[j].a-l));
}
ans++;
l = p[i].rgl;
r = p[i].rgr;
last_i = i;
}
}
for(int j=last_i;j<=n;j++)
{
p[j].newa = l;
p[j].newb = p[j].b - (p[j].m-(p[j].a-l));
}
ans++;
cout<<ans<<endl;
sort(p+1,p+1+n,cmp2);
for(int i=1;i<=n;i++)
{
cout<<p[i].a-p[i].newa<<" "<<p[i].b-p[i].newb<<endl;
}
}
return 0;
}
|