A. Serval and Bus
题意
给到达公交车站的时间t，n条公交路线，每条公交路线中包含第一班车到达的时间si、其后每班车之间的间隔di。
问能坐到的第一班车是在什么时候。
关键词
模拟
思路
对于每班车从si开始累加di，直到结果大于等于t时更新最小时间。
也可以不用累加，直接用公式求。
代码
#include <bits/stdc++.h>
#define Debug 0
#define MAXN 100005
#define MAXM 200
#define MAXK 10000010
#define MOD 6000
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int main ()
{
#ifdef FILE_IN
freopen(FILE_IN, "r", stdin);
#endif
int n,t;
cin>>n>>t;
vector<int> vt;
int ans =1;
int time = INT_MAX;
for (int i = 0; i < n; ++i)
{
int s,d;;
cin>>s>>d;
int j=0;
for (j = s; ; j+=d)
{
if(j>=t)
{
if (j<time)
{
ans = i+1;
time = j;
}
break;
}
}
}
cout<<ans<<endl;
#ifdef FILE_IN
fclose(stdin);
#endif
return 0;
} B. Serval and Toy Bricks
题意
给定三视图，还原出每一个水平位置上堆有多少个立方体。
关键词
模拟，贪心
思路
对于给定的三视图，以及水平坐标x，y，如果俯视图中（x，y）有方块，那么这个位置堆叠的立方体的数量就取 min{ 侧视图中该行的高度，正视图中该列的高度 }。
这样的解一定是满足给出的三视图的。
代码
#include <bits/stdc++.h>
#define Debug 0
#define MAXN 105
#define MAXM 200
#define MAXK 10000010
#define MOD 6000
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int n,m,h;
int front[MAXN], side[MAXN], top[MAXN][MAXN];
int ans[MAXN][MAXN] ={0};
int main ()
{
#ifdef FILE_IN
freopen(FILE_IN, "r", stdin);
#endif
cin>>n>>m>>h;
for (int i = 0; i < m; ++i)
{
cin>>front[i];
}
for (int i = 0; i < n; ++i)
{
cin>>side[i];
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
cin>>top[i][j];
}
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if(top[i][j])
{
ans[i][j] = min(front[j], side[i]);
}
cout<<ans[i][j]<<(j==m-1?"\n":" ");
}
}
#ifdef FILE_IN
fclose(stdin);
#endif
return 0;
} C. Serval and Parenthesis Sequence
题意
给一个长度为n、由(、)、?三种字符组成的序列，要求将?替换成(或)，使最终结果满足：
- 整个序列是一个有效的括号序列。
- 序列中任何一个严格前缀（不为空且不为这个序列本身）都不是一个有效的括号序列。
没有有效解就输出:(。
关键词
贪心
思路
对于给定的n，最后的结果中左括号和右括号个数一定都为n/2，再根据给出的序列求出左右括号还差多少个。
填充时，优先填左括号，左括号填完了再填右括号。
可以在填充时或者填充完成后检查一下其严格前缀是否为有效括号序列即可。
代码
#include <bits/stdc++.h>
#define Debug 0
#define MAXN 300005
#define MAXM 200
#define MAXK 10000010
#define MOD 6000
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int n;
int num[MAXN];
int main ()
{
#ifdef FILE_IN
freopen(FILE_IN, "r", stdin);
#endif
cin >> n;
string s;
cin >> s;
bool tag = 1;
int sum = 0;
int ll = n/2, rr= n/2;
for (int i = 0; i < n; ++i)
{
if(s[i] == '(')
{
sum++;
ll--;
}
else if(s[i] == ')')
{
sum--;
rr--;
}
num[i] = sum;
}
int l = 0;
if (s[0] == ')' || s[n - 1] == '(')
tag = 0;
for (int i = 0; i < n; ++i)
{
char c = s[i];
switch (c)
{
case '(':
l++;
break;
case '?':
if(ll>0)
{
s[i] = '(';
ll--;
l++;
} else
{
s[i] =')';
rr--;
l--;
if(l==0&& i !=n-1)
{
tag= 0;
}
}
break;
case ')':
l--;
if (l == 0 && i!=n-1)
{
tag = 0;
break;
}
break;
}
}
if (l!=0 || n%2==1)
tag = 0;
if (tag)
{
cout << s << endl;
} else
{
cout << ":(" << endl;
}
#ifdef FILE_IN
fclose(stdin);
#endif
return 0;
} D. Serval and Rooted Tree
题意
给定一包含n个节点棵树，其中叶子节点为k个。
对于每个非叶子节点，其值为子节点的最大值或最小值；对于每个叶子节点，为其分配[1,k]中的一个值，每个值只能分配给一个叶子节点。
求这棵树最大值为多少。
关键词
树形DP
思路
- 假设、定义：
ans：最终结果。
k：叶子节点的数量。
dp[i]：节点i的值为ans时，第i个节点为根子树中，大于等于ans节点的数量。
j:节点 i 的子节点。
将大于等于ans的值用1来表示。 - 状态转移：
i为叶子节点：dp[i]=1.
i为max：dp[i] = min {dp[j]}。
i为min：dp[i] = Σ {dp[j]}。 - 最终结果：
ans= k - dp[1] + 1 。 - 理解与解释：
- 对于单个叶子节点：能取得的最大值肯定为ans，所以值为1。
- 对于max节点：先回顾dp[i]的定义：大于等于ans的节点的数量，要当前节点能取得最大值，显然，比当前节点大的值数量越少，意味着当前节点值越大，故取子节点dp[i]的最小值。
- 对于min节点：与max节点同理，要使当前节点值最小，则是比当前节点值大的越多，意味着当前节点值越小，故求子节点dp[i]之和。
- 最终结果：依题意：1号节点为根节点，所有值中能取到的最大值为k。dp[1]就意味着对于整棵树而言，在[1, k]中大于等于ans的有dp[i]个。
再说直白点就是dp[1]表示ans为[1, k]中第几大的值。
所以为k - dp[1] + 1。
代码
#include <bits/stdc++.h>
#define Debug 0
#define MAXN 300005
#define MAXM 200
#define MAXK 10000010
#define MOD 6000
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int n;
int op[MAXN];
int cnt = 0;
int dp[MAXN];
vector<int> G[MAXN];
void dfs(int u)
{
if(G[u].empty())
{
cnt++;
dp[u] = 1;
}else
{
if(op[u] == 1)
{
dp[u] = INT_MAX;
for (int i = 0; i < G[u].size(); ++i)
{
int v = G[u][i];
dfs(v);
dp[u] = min(dp[u], dp[v]);
}
} else
{
dp[u] = 0;
for (int i = 0; i < G[u].size(); ++i)
{
int v = G[u][i];
dfs(v);
dp[u] += dp[v];
}
}
}
}
int main ()
{
#ifdef FILE_IN
freopen(FILE_IN, "r", stdin);
#endif
cin>>n;
for (int i = 1; i <= n; ++i)
{
cin>>op[i];
}
for (int i = 2; i <= n; ++i)
{
int t;
cin>>t;
G[t].pb(i);
}
dfs(1);
cout<<1+cnt-dp[1]<<endl;
#ifdef FILE_IN
fclose(stdin);
#endif
return 0;
} E. Serval and Snake
题意
在一个n*n的矩阵中，有一条蛇，这条蛇长度至少为2（一头一尾）。
每次可以询问一个矩形，会返回这个矩形的边界分隔了蛇的身体多少次。
要求在有限次的询问中，求出蛇的头和尾的位置。
关键词
二分
思路
这题有一个很重要的的性质：对于每次查询返回的值，如果为奇数，则表示询问的区间内恰好包含头部或尾部；如果返回的为偶数，则表示该区间内头部和尾部要么全部包含要么一个没有。
- 对每行每列进行询问，如果存在返回的值为奇数则保存该行或该列。显然，如果有，则这样的行或列一定成对出现，因为有一首一尾。
- 对于已保存的行和列，可以讨论如下三种情况：
行和列都存在：这意味着，首尾既不在同一行，也不在同一列，是最简单的一种情况，直接组合行和列的两个值即可。假设行为x1、x2，列为y1、y2，有2组合的结果有两种(x1,y1)(x2,y2)、(x1,y2)(x2,y1)，任意查询某种情况的一个点，如果返回值为偶数，则说明这种组合错误，取另一种即可。
只存在行：这种情况说明，头部和尾部在同一列不同行，行坐标已知，设为x1,x2，假设所在列都为y，在x1,x2中任取一行，在[1,n]的区间内二分枚举y即可。
【二分思路】：询问(x1,1)(x1,y)这个区间，返回为奇数则说明在[1,y]内存在头部或尾部，将y向靠近左半区间，否则说明不在这个区间内，将y靠近右半区间。
只存在列：类似于只存在行的情况，对公共行进行二分枚举即可。
对前面性质的分析解释
- 如果两个端点（头部和尾部）只有一个在这个区间内：要通向另一个端点，必然是有一条路出去的，蛇的身体其他部分如果也穿过这个区间，必然是“有进有出”的，贡献的次数为偶数次，可以不去讨论，只考虑连向端点的部分。
区间内只有一个端点 - 如果两个端点都在这个区间内、或者都不在：那么会贡献次数的，只有第一点中提到的身体部分，次数一定为偶数，或者为0.
2个端点都在、都不在区间内
如此求解，询问次数为2*n+log~2~n，n最大为1000时，也不过2010，不会超过题目的限制。
代码
#include <bits/stdc++.h>
#define Debug 0
#define MAXN 300005
#define MAXM 200
#define MAXK 10000010
#define MOD 6000
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;
using namespace std;
int n;
int ask (int x1, int y1, int x2, int y2)
{
cout << "? " << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
cout.flush();
int t;
cin >> t;
return t;
}
int main ()
{
#ifdef FILE_IN
freopen(FILE_IN, "r", stdin);
#endif
vector<int> row, col;
cin >> n;
for (int i = 1; i <= n; ++i)
{
int r = ask(i, 1, i, n);
int c = ask(1, i, n, i);
if (r % 2)
{
row.pb(i);
}
if (c % 2)
{
col.pb(i);
}
}
int x1, x2, y1, y2;
int l = 1, r = n;
if (row.size() && col.size())
{
// The head and tail in different rows and columns
x1 = row[0], x2 = row[1];
y1 = col[0], y2 = col[1];
if(ask(x1,y1,x1,y1)%2 == 0)
{
swap(y1,y2);
}
} else if (row.size())
{
// In different rows but same column
x1 = row[0], x2 = row[1];
while (l < r)
{
int m = (l + r) >> 1;
if (ask(x1, 1, x1, m) % 2)
{
r = m;
} else
{
l = m + 1;
}
}
y1 = y2 = l;
} else
{
// In different columns but same row
y1 = col[0], y2 = col[1];
while (l < r)
{
int m = (l + r) >> 1;
if (ask(1, y1, m, y1) % 2)
{
r = m;
} else
{
l = m + 1;
}
}
x1 = x2 = l;
}
cout << "! " << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
#ifdef FILE_IN
fclose(stdin);
#endif
return 0;
} 
京公网安备 11010502036488号