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_pairusing 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_pairusing 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_pairusing 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;
}