- define时间:
#define int long long
#define ind long double
#define yes cout << "Yes"
#define no cout << "No"
#define pii pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define pci pair<char, int>
#define re return;
#define rep(l, i, r) for (int i = l; i <= r; i++)
#define lep(r, i, l) for (int i = r; i >= l; i--)
The 3rd Universal Cup. Stage 23: Hong Kong - Dashboard - Contest - QOJ.ac
C. The Story of Emperor Bie
签到,题目本质找出最大值的位置。
void solve()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}x = *max_element(a + 1, a + 1 + n);num = 0;vector<int> v;for (int i = 1; i <= n; i++){if (a[i] == x){v.emplace_back(i);}}for (auto i : v){cout << i << ' ';}
}
K. LR String
思维。
题意:给一个由 L R 组成的字符串s1,可以操作任意次:删去L左边的字符或R右边的字符。
k次询问,每次给一个s2,问s2能否由s1变换得到。
思路:首先容易发现,只能删去L左边的字符或R右边的字符,所以如果L在首位或者R在末尾一定无法被删去。
而其他情况都可以被删去,这意味着只要s2是s1的子序列,我们必然可以通过删去得到它。
于是问题转变成判断s2是否为s1的子序列。
预处理一下s1每个位置的下一个 L R 位置,然后用s2模拟即可。
void solve()
{cin >> s1;cin >> k;n = s1.size();vector<int> l(n, n + 1), r(n, n + 1);int l1 = n + 1, r1 = n + 1;for (int i = n - 1; i >= 0; i--){l[i] = l1, r[i] = r1;if (s1[i] == 'L'){l1 = i;}else{r1 = i;}}while (k--){cin >> s2;bool ok = 1;if ((s1[0] == 'L' && s2[0] != 'L') || (s1.back() == 'R' && s2.back() != 'R')){cout << "NO\n";continue;}auto pos = (s2[0] == 'R' ? r1 : l1);if (pos > n - 1){cout << "NO\n";continue;}for (int i = 1; i < s2.size(); i++){if (s2[i] == 'R'){pos = r[pos];}else{pos = l[pos];}if (pos > n - 1){ok = 0;break;}}cout << (ok ? "YES\n" : "NO\n");}
}
L. Flipping Paths
模拟,思维。
题意:给一个BW组成的n*m的二维图,每次从起点到终点只可往右往下移动画出一条线,线上的字符改变,问能否在400次以内将所有字符变成相同。
思路:分别考虑将所有变成B或W。
每次找到当前行最右边一个不合法的作为当前行的终点,从起点到终点改变字符;
到终点后不是最后一行就下移,然后循环判断。
是最后一行就右移直至终点。
void solve()
{cin >> n >> m;vector a(n + 1, vector<char>(m + 1));rep(1, i, n){rep(1, j, m){cin >> a[i][j];}}auto check = [&](auto c){vector b(n + 1, vector<int>(m + 1));rep(1, i, n){rep(1, j, m){b[i][j] = (a[i][j] == c ? 1 : 0);}}vector<string> ans;int op = 0;while (op <= 410){auto ok = 1;rep(1, i, n){rep(1, j, m){if (b[i][j] != 1){ok = 0;break;}if (!ok)break;}}if (ok)break;string s = "";int st = 1; // 起始列rep(1, i, n) // 枚举行{b[i][st] ^= 1;int ed = 1; // 终止列lep(m, j, 1){if (b[i][j] == 0) //找终点{ed = j;break;}}while (st < ed) //走到终点{st++;b[i][st] ^= 1;s += 'R';}if (i != n) //不是最后一行就下移{s += 'D';}else //是最后一行且不是最后一列就右移{while (st < m){st++;b[i][st] ^= 1;s += 'R';}}}ans.emplace_back(s);op++;}if (op <= 400){cout << "YES\n";cout << op << '\n';for (auto u : ans){cout << u << '\n';}return 1;}return 0;};if (check('W') || check('B')){re;}else{cout << "NO\n";}
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);int T;T = 1;cin >> T;while (T--){solve();cout << '\n';}return 0;
}