【LGR-199-Div.3】复旦勰码基础赛 #16 & FSLOI Round 1
P11076 「FSLOI Round I」单挑
思路
最多连续胜利的场数最少是多少，其实就是在剩余的S里面插入F的连续胜场的最大值是多，以为要先小S获胜，可以插入的空的数量就是剩余S的大小，平均值上取整就是答案。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#define endl '\n'
#define ll long long
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define all(a) a.begin(), a.end()
#define lowbit(x) x & -x
#define ent cout << '\n'
#define out(x) cout << x << ' '
#define out2(x, y) cout << x << " ~ " << y << ' '
#define me(a, b) memset(a, b, sizeof a)
#define mc(a, b) memcpy(a, b, sizeof a)
#define pk push_back
#define ur(x) sort(all(x)), x.erase(unique(all(x)), x.end())
#define fi first
#define se second
#define si(x) int(x.size())
#define chi(x) (x - '0')
#define ull unsigned long long
#define Mp make_pair
using namespace std;
const ll inf = 1e18;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1);
const int mod = 998244353;
const int P = 1e9 + 7;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {-1, 1, 0, 0};
const int N = 1e6 + 10;
const int M = 1000 + 10;
int n, x, y;
void solve()
{
cin >> n >> x >> y;
string s;
cin >> s;
for (int i = 0; i < si(s); i ++)
if (s[i] == 'F') x --;
else y --;
cout << (x + y - 1) / y << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t --) solve();
return 0;
}
P11077 「FSLOI Round I」石子
思路
不可行的情况明显是对于一个不等于平均值的数，无论如何加减k值都不可能到达平均值。
接下讨论可行情况的胜负，明显的对于一个不等于平均值的数，可以进行的操作数是（平均值-它）/k，因为是同时操作两个数，所以最后总操作数要除以2，所以操作数是奇数的话先手必胜，偶数后手必胜。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#define endl '\n'
#define ll long long
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define all(a) a.begin(), a.end()
#define lowbit(x) x & -x
#define ent cout << '\n'
#define out(x) cout << x << ' '
#define out2(x, y) cout << x << " ~ " << y << ' '
#define me(a, b) memset(a, b, sizeof a)
#define mc(a, b) memcpy(a, b, sizeof a)
#define pk push_back
#define ur(x) sort(all(x)), x.erase(unique(all(x)), x.end())
#define fi first
#define se second
#define si(x) int(x.size())
#define chi(x) (x - '0')
#define ull unsigned long long
#define Mp make_pair
using namespace std;
const ll inf = 1e18;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1);
const int mod = 998244353;
const int P = 1e9 + 7;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {-1, 1, 0, 0};
const int N = 1e6 + 10;
const int M = 1000 + 10;
int n, k;
ll a[N];
void solve()
{
cin >> n >> k;
ll sum = 0;
for (int i = 1; i <= n; i ++) cin >> a[i], sum += a[i];
ll ave = sum / n;
bool flag = 0;
ll cnt = 0;
for (int i = 1; i <= n; i ++)
{
int num = abs(a[i] - ave);
if (num % k) {
flag = 1;
break;
}
else {
cnt = cnt + num / k;
}
}
if (flag) {
cout << "Draw" << '\n';
return ;
}
cnt = (cnt + 1) / 2;
if (cnt % 2) cout << 'F' << '\n';
else cout << "L" << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t --) solve();
return 0;
}
P11078 「FSLOI Round I」迷雾
思路
明显按照题意模拟必定超时，但观察发现对于同一个移动进行偶数次操作是不变的，所以考虑用差分，当进入一个迷雾时将所有要操操作的移动进行一次标记就是：\(C_{i+k}+1,C_{i+b_{i}*k + k}-1\)，因为只有间隔k的数进行差分，前缀和的时候也只从间隔为k的数转移过来。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#define endl '\n'
#define ll long long
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define all(a) a.begin(), a.end()
#define lowbit(x) x & -x
#define ent cout << '\n'
#define out(x) cout << x << ' '
#define out2(x, y) cout << x << " ~ " << y << ' '
#define me(a, b) memset(a, b, sizeof a)
#define mc(a, b) memcpy(a, b, sizeof a)
#define pk push_back
#define ur(x) sort(all(x)), x.erase(unique(all(x)), x.end())
#define fi first
#define se second
#define si(x) int(x.size())
#define chi(x) (x - '0')
#define ull unsigned long long
#define Mp make_pair
using namespace std;
const ll inf = 1e18;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1);
const int mod = 998244353;
const int P = 1e9 + 7;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {-1, 1, 0, 0};
const int N = 1e6 + 10;
const int M = 1000 + 10;
int n, m, k, q;
int cc[N];
char g[M][M];
struct node {
char op;
int a, b;
} o[N];
void dfs(int x, int y, int step)
{
if (step > q) {
cout << x << ' ' << y << '\n';
return ;
}
// 前缀和，注意要进行前缀的数组，安间隔k分组
cc[step] += cc[step - k];
char op = o[step].op;
int a = o[step].a;
// 偶数次操作是不变，这里判断奇数次时改变移动方向
if (cc[step] % 2) {
if (op == 'U') op = 'D';
else if (op == 'D') op = 'U';
else if (op == 'L') op = 'R';
else op = 'L';
}
if (op == 'U') {
x -= a;
if (x < 1) x = 1;
}
else if (op == 'D') {
x += a;
if (x > n) x = n;
}
else if (op == 'L') {
y -= a;
if (y < 1) y = 1;
}
else {
y += a;
if (y > m) y = m;
}
if (g[x][y] == 'X') {
if (o[step].b > 0) {
// 差分
int l = k + step, r = k * o[step].b + step;
cc[l] ++;
cc[r + k] --;
}
}
dfs(x, y, step + 1);
}
void solve()
{
cin >> n >> m >> q >> k;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
cin >> g[i][j];
for (int i = 1; i <= q; i ++)
cin >> o[i].op >> o[i].a >> o[i].b;
dfs(1, 1, 1);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t --) solve();
return 0;
}
P11079 「FSLOI Round I」山峦
不会，看下官方题解吧
贴一份官方题解的代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int n,a[510],f1[510][510]={0},f2[510][510]={0},dp[510]={0};
int sum[1000010];
int solve(int l,int r){
int ans=0;
for(int i=l+1;i<=r-1;i++){
if(f1[l][i]&&f2[r][i]) ans=(ans+f1[l][i]*f2[r][i]%mod-1+mod)%mod;
ans=(ans+sum[a[i]]*f2[r][i]%mod)%mod;
sum[a[i]]=(sum[a[i]]+f1[l][i])%mod;
}
for(int i=l+1;i<=r-1;i++) sum[a[i]]=0;
return ans;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
f1[i][i]=1;
for(int j=i+1;j<=n;j++){
for(int k=i;k<=j-1;k++){
if(a[k]>a[j]) f1[i][j]=(f1[i][j]+f1[i][k])%mod;
}
}
}
for(int i=n;i>=1;i--){
f2[i][i]=1;
for(int j=i-1;j>=1;j--){
for(int k=j+1;k<=i;k++){
if(a[k]>a[j]) f2[i][j]=(f2[i][j]+f2[i][k])%mod;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i-1;j++) dp[i]=(dp[i]+f2[i][j])%mod;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i-3;j++){
if(a[j]>=a[i]) continue;
dp[i]=(dp[i]+dp[j]*solve(j,i)%mod)%mod;
}
}
int ans=0;
for(int i=1;i<=n;i++){
int Sum=0;
for(int j=i+1;j<=n;j++) Sum=(Sum+f1[i][j])%mod;
ans=(ans+Sum*dp[i]%mod)%mod;
}
cout<<ans<<endl;
return 0;
}