个人题解
A
log库函数
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int score;
cin>>score;
cout<<150*log(score)<<'\n';
return 0;
}
B
找规律
#include <iostream>
using namespace std;
int main() {
int n;
cin>>n;
cout<<n/5*2<<' ';
cout<<n/20*2 + (n%20 >= 5) + (n%20 >= 15)<<' ';
cout<<n/20*3<<' ';
cout<<n*2 - n/20*2<<'\n';
return 0;
}
C
位运算
#include <iostream>
using namespace std;
int main() {
long long n;
cin>>n;
cout<<((1ll<<64-__builtin_clzll(n))-1)<<'\n';
return 0;
}
D
偶数不行 因为1所在区间gcd必是1 按位或后的结果最低位必是1
否则 只要m二进制位数小于等于n 都可构造
构造方法是 分为k=__builtin_popcount(m)组
- 对于m的除最低位以外的k-1个二进制位 令每位对应的2的幂单独成组 作为m的高k-1位
- 其余所有数共同成一组 其gcd必是1 作为m的最低1位
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
int n,m;
cin>>n>>m;
if (m%2 == 0 || __builtin_clz(m) < __builtin_clz(n)) {
cout<<-1<<'\n';
return 0;
}
int len = 32-__builtin_clz(m);
unordered_set<int> st;
for (int i=1; i<len; i++)
if (m>>i&1)
cout<<(1<<i)<<' ', st.insert(1<<i);
for (int i=1; i<=n; i++)
if (st.find(i) == st.end())
cout<<i<<' ';
cout<<'\n';
cout<<__builtin_popcount(m)<<'\n';
for (int i=1; i<=st.size(); i++)
cout<<i<<' '<<i<<'\n';
cout<<st.size()+1<<' '<<n<<'\n';
return 0;
}
E
高中数学题
对于
求导得
单调递增
- 当
时
,
在
上单调递增
- 当
时
令
得
即
当时,
,
在
上单调递减
当时,
,
在
上单调递增
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
double p[100005][2];
int main() {
int n;
cin>>n;
for (int i=1; i<=n; i++)
cin>>p[i][0]>>p[i][1];
double ans = 0;
for (int i=2; i<=n; i++) {
double e = sqrt(pow(p[i][0]-p[i-1][0], 2) + pow(p[i][1]-p[i-1][1], 2));
if (e < 1/log(2))
ans += 2*e;
else
ans += 2*log2(e*log(2)) + 2/log(2);
}
cout<<fixed<<setprecision(9)<<ans<<'\n';
return 0;
}
F
还是找规律 找规律+快速幂+前缀和
m只有1e6 由于每次的结果只与当前的c有关 故一定会有循环节
但是注意不一定从第一个数循环
注意b很大 可以一开始先对b取一次模
注意k小于循环节开始下标时要特殊处理
注意中间结果不要溢出 不要溢出long long
如果中间过程出现了负数 还要注意负数取模的问题
#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;
long long m;
long long pow(long long b, long long c) {
return c?pow(b*b%m,c/2)*(c%2?b:1)%m:1;
}
int main() {
long long b,c;
int q;
cin>>b>>c>>m>>q;
b %= m;
vector<int> vec;
unordered_set<int> st;
while (st.find(c = pow(b,c)) == st.end())
vec.push_back(c), st.insert(c);
int p = find(vec.begin(), vec.end(), c) - vec.begin();
int n = vec.size();
vector<long long> s(n+1);
for (int i=1; i<=n; i++)
s[i] = s[i-1]+vec[i-1];
while (q--) {
long long k;
cin>>k;
if (k <= n)
cout<<s[k]%m<<'\n';
else
cout<<(s[p] + (k-p)/(n-p)%m*((s[n]-s[p])%m) + s[p+(k-p)%(n-p)] - s[p])%m<<'\n';
}
return 0;
}