官方题解| ACGO挑战赛#10
2024-10-08 10:01:17
发布于：福建
ACGO挑战赛#10
来源：出题人wtcqwq题解
T1、ytiroirp
按题目模拟即可。
这道题需要注意位运算的优先级很低，远低于四则运算。
换句话说 1+1|2 被理解为 2|2=2，尽管你可能想写的是 1+(1|2)=1+3=4。
关于人名，Ytiroirp 反过来写，即 priority ，含义为优先，就在提示你易错点。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=100009;
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll a,b;
cin>>a>>b;
cout<<((a&b)+(a|b)+(a^b))<<endl;
return 0;
}
T2、Elbisivid
题目大意：站在数轴原点，可以走任意不是 倍数的步幅，求最小步数走到点 。
题解：如果 是 的倍数，你先走 ，转化成不是 的倍数即可。
如果 不是 的倍数，直接走即可。
换句话说，答案至多为 。
与上题类似的，Elbisivid 反转即为 divisible，也是本题题意&解题方法的关键。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=100009;
ll n,a[N];
void solve(){
ll n,k;
cin>>n>>k;
if(n%k!=0) cout<<1<<endl;
else cout<<2<<endl;
}
int main(){
ll t; cin>>t;
while(t--) solve();
return 0;
}
T3、Lscumm
容易想到，可以用两个互质的 的因数使得 lcm 为 。由于对序列长度没有限制，所以剩下的都用 来填充使得和达到 。所以问题就转化成了判断 有没有两个互质的因数。
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;scanf("%d",&t);
while(t--){
int n;scanf("%d",&n);
int cnt=0;
for(int i=2;i*i<=n;i++){
if(n%i==0){
cnt++;
while(n%i==0)n/=i;
}
}
if(n>1)cnt++;
if(cnt>1)puts("Yes");
else puts("No");
}
return 0;
}
T4、Distinct
考虑改变钦定顺序，从 小往大钦定。
显然前面选过的一定会对当前可以选的数量造成影响。
所以将 排序后，答案即为 。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=200009,mod=998244353;
int main(){
int t; cin>>t;
while(t--){
ll n; cin>>n;
vector<ll> v;
for(ll i=1;i<=n;i++){
ll x; cin>>x;
v.push_back(x);
}
ll ans=1;
sort(v.begin(),v.end());
for(ll i=0;i<n;i++){
ans*=(v[i]-i);
// cout<<v[i]<<" "<<i<<endl;
ans%=mod;
}
cout<<ans<<endl;
}
}
T5、dloonc
-
如果要想让火炉燃烧时间少，就得在无客人到访的时候熄灭。
-
如果要想让火炉燃烧时间更少，就得让所有的火柴都用上，也就是尽可能多的打开熄灭。
-
如果要想让火炉燃烧的时间最少，就得在客人到访时间间隔最长的时候熄灭，打开火炉。
总而言之，让每次打开熄灭，让每根火柴发挥最大用处。
如果中途不熄灭炉火，从第一位客人来访到最后一位客人离开，炉火运行时间是： 。(因为第一位客人到访后还有1的访问时间)
贪心算法，就要尽可能的在时间间隔大两次访问之间熄灭炉火，所以也要推导出访问间隔公式： 。(因为其中夹杂着第一位客人的到访时间）
把间隔时间存储在数组里，用 sort 从大到小排序，在依照火柴数量减去相应的间隔时间。
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 100005
using namespace std;
int n,k,a[N];
int main(){
scanf("%d%d",&n,&k);k--;
rep(i,1,n)scanf("%d",&a[i]);
int ans = a[n] - a[1] + 1;
rep(i,1,n)a[i] = a[i + 1] - a[i] - 1;
sort(a+1,a+n);rep(i,1,k)ans -= a[n - i];
printf("%d\n",ans);return 0;
}
T6、Ptorrweee
考虑欧拉序，在欧拉序（dfs 序）下，子树是连续区间。
考虑怎么处理 的约束，可以制约成 ，也就是 。
整个式子就是 ，可以拆分成 。
对于每一个点 ，前一项是可以提出来的。所以只需要加后面的 即可。转化成一般的子树加问题，用欧拉序+树状数组解决。
又，因为 有可能 ，需要处理分数取模问题。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=400009;
ll n,m,a;
vector<ll> to[N];
ll sz[N],dfn[N],cnt,d[N];
const ll mod=998244353;
struct BIT {
int n;
vector<ll> w;
BIT() {}
BIT(ll n) {
this->n = n;
w.resize(n + 1);
}
void add(ll x, ll k) {
k%=mod; k+=mod; k%=mod;
for (; x <= n; x += x & -x) {
(w[x] += k)%=mod;
w[x]+=mod; w[x]%=mod;
}
}
void add(ll x, ll y, ll k) {
k%=mod; k+=mod; k%=mod;
add(x, k), add(y+1, -k);
}
ll ask(ll x) {
ll ans = 0;
for (; x; x -= x & -x) {
(ans += w[x])%=mod;
ans+=mod; ans%=mod;
}
return ans;
}
};
void dfs(ll u,ll fa){
d[u]=d[fa]+1;
sz[u]=1;
dfn[u]=++cnt;
for(auto v:to[u]){
if(v==fa) continue;
dfs(v,u);
sz[u]+=sz[v];
}
}
ll qpow(ll x,ll y){
x%=mod; x+=mod; x%=mod;
if(y==0) return 1ll;
if(y<0) return qpow(qpow(x,-y),mod-2);
ll ans=1ll;
while(y){
if(y&1) (ans*=x)%=mod;
(x*=x)%=mod;
y>>=1ll;
}
return ans;
}
int main(){
// freopen("data07.in","r",stdin);
// freopen("data07.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m>>a;
BIT Q(n+1);
for(ll i=2;i<=n;i++){
ll u,v; cin>>u>>v;
to[u].push_back(v);
to[v].push_back(u);
}
d[0]=-1;
dfs(1,0);
for(ll i=1;i<=m;i++){
cerr<<"ok\n";
ll opt,v,x;
cin>>opt>>v;
if(opt==1){
cin>>x;
Q.add(dfn[v],dfn[v]+sz[v]-1,qpow(a,-d[v]+x));
}
else cout<<(Q.ask(dfn[v])*qpow(a,d[v])%mod+mod)%mod<<endl;
}
return 0;
}
有帮助，赞一个