问题 A
时间限制: 1Sec 内存限制: 128MB 提交: 101 解决: 19
题目描述
小蓝有一个 01 串 s = s1 s2 s3 · · · sn。
以后每个时刻，小蓝要对这个 01 串进行一次变换。每次变换的规则相同。
对于 01 串 s = s1 s2 s3 · · · sn，变换后的 01 串 s′ = s′1 s′2 s′3· · · s′n 为：
s′1 = s1;
s′i = sii 1 ⊕ si。
其中 a ⊕ b 表示两个二进制的异或，当 a 和 b 相同时结果为 0，当 a 和 b不同时结果为 1。
请问，经过 t 次变换后的 01 串是什么？
输入
输入的第一行包含两个整数 n, t，分别表示 01 串的长度和变换的次数。
第二行包含一个长度为 n 的 01 串。
输出
输出一行包含一个 01 串，为变换后的串。
样例输入
5 3
10110
样例输出
11010
#include <bits/stdc++.h> #define ll long long using namespace std; string a; ll n,t,v[107]; int main() { v[0]=1; for (ll i=1;i<=60;i++) v[i]=v[i-1]<<1; cin>>n>>t; for (ll i=1;i<=60;i++) { if (n>v[i-1] && n<=v[i]) { t%=v[i]; break; } } if (n==1) t=0; cin>>a; while (t--) { for (ll i=n-1;i>=1;i--) { if (a[i]=='1' && a[i-1]=='0') a[i]='1'; else if (a[i]=='0' && a[i-1]=='1') a[i]='1'; else a[i]='0'; } } cout<<a<<endl; return 0; }
问题 B
时间限制: 1Sec 内存限制: 128MB 提交: 2 解决: 0
题目描述
一片海域上有一些冰山，第 i 座冰山的体积为 Vi。
随着气温的变化，冰山的体积可能增大或缩小。第 i 天，每座冰山的变化量都是 Xi。当 Xi > 0 时，所有冰山体积增加 Xi；当 Xi < 0 时，所有冰山体积减少 ቁ Xi；当 Xi = 0 时，所有冰山体积不变。
如果第 i 天某座冰山的体积变化后小于等于 0，则冰山会永远消失。
冰山有大小限制 k。如果第 i 天某座冰山 j 的体积变化后 Vj 大于 k，则它会分裂成一个体积为 k 的冰山和 Vj 赗? k 座体积为 1 的冰山。第 i 天结束前（冰山增大、缩小、消失、分裂完成后），会漂来一座体积为Yi 的冰山（Yi = 0 表示没有冰山漂来）。
小蓝在连续的 m 天对这片海域进行了观察，并准确记录了冰山的变化。小蓝想知道，每天结束时所有冰山的体积之和（包括新漂来的）是多少。
由于答案可能很大，请输出答案除以 998244353 的余数。
输入
输入的第一行包含三个整数 n, m, k，分别表示初始时冰山的数量、观察的
天数以及冰山的大小限制。
第二行包含 n 个整数 V1, V2, · · · , Vn，表示初始时每座冰山的体积。
接下来 m 行描述观察的 m 天的冰山变化。其中第 i 行包含两个整数 Xi, Yi，
意义如前所述。
输出
输出 m 行，每行包含一个整数，分别对应每天结束时所有冰山的体积之和
除以 998244353 的余数。
样例输入
1 3 6
1
6 1
2 2
-1 1
样例输出
8
16
11
提示
【样例说明】
在本样例说明中，用 [a1, a2, · · · , an] 来表示每座冰山的体积。
初始时的冰山为 [1]。 第 1 天结束时，有 3 座冰山：[1, 1, 6]。 第 2 天结束时，有 6 座冰山：[1, 1, 2, 3, 3, 6]。 第 3 天结束时，有 5 座冰山：[1, 1, 2, 2, 5]。
【评测用例规模与约定】
对于 40% 的评测用例，n, m, k ≤ 2000；
对于 60% 的评测用例，n, m, k ≤ 20000；
对于所有评测用例，1 ≤ n, m ≤ 100000, 1 ≤ k ≤ 109, 1 ≤ Vi ≤ k, 0 ≤ Yi ≤ k,쇋? k ≤ Xi ≤ k。
目前找不到完全正确的代码
#include<bits/stdc++.h> using namespace std; #define INF 1e18 typedef long long LL; const int maxn=1e5+10; LL ans=0,mod=998244353; vector<LL>g; int main(){ iostream::sync_with_stdio(false); int n,m,k; cin>>n>>m>>k; for(int i=1;i<=n;i++){ LL v; cin>>v; g.push_back(v); ans+=v; } for(int i=1;i<=m;i++){ LL x,y,len=g.size(); cin>>x>>y; for(int j=0;j<len;j++){ g[j]+=x; if(g[j]<=0) g.erase(j+g.begin()); else if(g[j]>k){ for(int cnt=1;cnt<=g[j]-k;cnt++) g.push_back(1); g[j]=k; } } if(y>0) g.push_back(y); ans+=(x*len+y)%mod; cout<<ans<<endl; } return 0; }
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll N=1e5+10,mod=998244353; vector<ll>g; vector<ll> f(vector<ll> t,ll x,ll y,ll k) { vector<ll>res; ll sz=(ll)t.size(); for(ll i=0;i<sz;i++) { t[i]+=x; if(t[i]>0) // 只保留大于0的 { if(t[i]<=k)res.push_back(t[i]); else // 分裂 { res.push_back(k); for(ll j=1;j<=t[i]-k;j++) // 没想到这里怎么优化 res.push_back((ll)1); } } } if(y>0)res.push_back(y); return res; } int main() { ios::sync_with_stdio(false); ll n,m,k,x,y; cin>>n>>m>>k; for(ll i=1;i<=n;i++) { cin>>x; g.push_back(x); } for(ll i=1;i<=m;i++) { cin>>x>>y; g=f(g,x,y,k); ll sum=0; for(ll j=0;j<g.size();j++) sum=(sum+g[j])%mod; printf("%lld\\n",sum); } return 0; }
