|
文章目录
1001 签到 数学 模拟1002 随机题意 思维1003 魔怔 图论 欧拉回路1004 净化 数学，思维
题目地址
2021 年百度之星·程序设计大赛 - 初赛二
题目原地址
2021 年百度之星·程序设计大赛 - 初赛二
1001 签到 数学 模拟
题目地址1001 签到 题意：给a,b ，每次 a,b 会变为a+b,a−b ，问 k 次之后变成了哪两个数，对998244353 取模，多组数据。 思路：模拟一下，算几个数，发现是有规律的，如果k是奇数，结果就是
(
a
+
b
)
∗
2
k
/
2
m
o
d
m
o
,
(
a
−
b
+
m
o
)
∗
2
k
/
2
m
o
d
m
o
(a+b)*2^{k/2}\mod mo,(a-b+mo)*2^{k/2}\mod mo
(a+b)∗2k/2modmo,(a−b+mo)∗2k/2modmo,这里a-b需要加一个mo保证他是正数，因为对负数取模还是负数，我在这里卡了好几发。如果k是偶数就是
a
k
/
2
m
o
d
m
o
b
k
/
2
m
o
d
m
o
a^{k/2}\mod mo b^{k/2}\mod mo
ak/2modmobk/2modmo就好了，用个快速幂就好了。 AC代码：
#include
#define ll long long
using namespace std;
const ll mo = 998244353;
ll qpow(ll a, ll n,ll m){
ll ans = 1;
while(n){
if(n&1)
{
ans = a * ans % m;
}
a = a * a % m;
n >>= 1;
}
return ans;
}
void solve()
{
ll a, b, k;
scanf("%lld%lld%lld",&a,&b,&k);
ll x = qpow(2,k/2,mo);
ll ans1, ans2;
if(k%2)
{
ans1 = (a+b)%mo*x%mo;
ans2 = (a-b+mo)%mo*x%mo;
printf("%lld %lld",ans1,ans2);
}
else
{
ans1 = a%mo*x%mo;
ans2 = b%mo*x%mo;
printf("%lld %lld",ans1,ans2);
}
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int t;
scanf("%d",&t);
for(int i =1;i
int l,r;
bool operator
int n, k;
cin >> n >> k;
priority_queue pqq;
vector vq;
for(int i = 1;i
qujian q1 = pqq.top();
pqq.pop();
if(pqq.empty())
{
vq.push_back(q1);
break;
}
else
{
qujian q2 = pqq.top();
if(q1.r >= q2.l)
{
q1.r = q2.r;
pqq.pop();
pqq.push(q1);
}
else
{
vq.push_back(q1);
}
}
}
ll ans = 0;
for(int i = 0;i
cout
solve();
}
return 0;
}
1003 魔怔 图论 欧拉回路
题目地址1003 魔怔
参考地址 2021 年百度之星·程序设计大赛 - 初赛二 1003 魔怔（并查集，联通性，欧拉回路） AC代码：
//没补完.jpg
#include
using namespace std;
typedef long long LL;
const int maxn = 1010;
int fa[maxn+10];
void init(int n){for(int i = 1; i x=find(x);y=find(y);if(x!=y)fa[x]=y;}
int e[maxn][maxn], in[maxn];
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T; cin>>T;
while(T--){
memset(e,0,sizeof(e));
memset(in,0,sizeof(in));
int n, rt; cin>>n>>rt;
int cnt = 0; init(n);
for(int i = 2; i
e[i][j+1] = e[j+1][i]= s[j]-'0';
if(e[i][j+1]==0){
cnt++;
in[i]++; in[j+1]++;//累加度数
merge(i,j+1);
}
}
}
//cout
int s = find(i);
if(mp[s]==0){ok++; mp[s]=1;}
}
}
if(sum==0){cout
if(in[rt]){//在
if(in[rt]%2==0){//偶数
if(ans)cout//不在
if(ans==0)cout
int n;
ll m;
bool flag = false;
cin >> n >> m;
ll minx = 0,maxx = 0;
for(int i = 1;i
sum1[i] = 0;
}
maxx = max(maxx,sum12[i]);
if(sum1[i] >= m)
{
flag = 1;
}
}
if(flag)
{
cout
ans = 2;
}else
{
ans = ceil((m - maxx - b * 1.0)/(sum12[n])) + 2;
}
}
else
{
b = sum1[n];
sum2[0] = b;
for(int i = 1;i
sum2[i] = 0;
}
if(sum2[i] >= m)
{
ans = 2;
}
}
if(!ans)
{
ans = -1;
}
}
cout
solve();
}
return 0;
}
|