#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
int T,cc = 0;
scanf("%d",&T);
while(T --) {
int n;
scanf("%d",&n);
int ans = 0;
for(int i = 1,r;i <= n;i = r + 1) {
r = n / (n / i);
ans += (r-i+1ll) * (n / i) & 1;
}
if(ans&1) printf("Case %d: odd\n",++ cc);
else printf("Case %d: even\n",++ cc);
}
}
B
基础模拟。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
int T,cc = 0;
scanf("%d",&T);
map<string,int> mp;
mp["Beijing"] = 8;
mp["Washington"] = -5;
mp["London"] = 0;
mp["Moscow"] = 3;
while(T --) {
int h,m;
string s,name1,name2;
scanf("%d:%d",&h,&m);
cin >> s >> name1 >> name2;
h %= 12;
if(s == "PM") h += 12;
int delta = mp[name2] - mp[name1];
h += delta;
//cout << h << endl;
string rq;
if(h >= 24) rq = "Tomorrow";
else if(h < 0) rq = "Yesterday";
else rq = "Today";
h += 24; h %= 24;
string ans;
if(h <= 11) ans = "AM";
else ans = "PM",h -= 12;
if(h == 0) h = 12;
printf("Case %d: %s %d:%02d %s\n",++ cc,rq.c_str(),h,m,ans.c_str());
}
}
C
基础贪心。也可以写并查集。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int SZ = 2e5 + 10;
int bel[SZ],tot,sum,mark[SZ];
vector<int> g[SZ];
void dfs(int u,int c) {
bel[u] = c;
for(int v : g[u]) {
dfs(v,c);
}
}
int main() {
int T,cc = 0;
scanf("%d",&T);
while(T --) {
int n;
scanf("%d",&n);
for(int i = 1;i <= tot;i ++) {
bel[i] = 0;
mark[i] = 0;
g[i].clear();
}
tot = n,sum = 0;
priority_queue<pii> q;
for(int i = 1;i <= n;i ++) {
int x;
scanf("%d",&x);
q.push(make_pair(x,i));
}
while(q.size()) {
pii p = q.top(); q.pop();
if(p.first <= 1) { mark[p.second] = 1; sum ++; continue; }
if(q.size()) {
pii p2 = q.top(); q.pop();
if(p2.first == p.first) {
pii ans = make_pair(p.first-1,++ tot);
//printf("%d -> %d\n",tot,p.second);
// printf("%d -> %d\n",tot,p2.second);
g[tot].push_back(p.second);
g[tot].push_back(p2.second);
q.push(ans);
}
else q.push(p2);
}
}
if(sum < 2) {
printf("Case %d: NO\n",++ cc);
}
else {
printf("Case %d: YES\n",++ cc);
int t = 0;
for(int i = 1;i <= tot;i ++) {
if(mark[i]) {
dfs(i,t);
if(t==0) t++;
}
}
for(int i = 1;i <= n;i ++) printf("%d",bel[i]); puts("");
}
}
}
D
基础概率DP。由于会加1.5%所以状态要乘2。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int SZ = 2e5 + 10;
double f[333];
int main() {
int T,cc = 0;
scanf("%d",&T);
while(T --) {
int pp;
scanf("%d",&pp);
double p = 1.0*pp/100;
f[200] = 1/p;
for(int i = 199;i >= 4;i --) {
int nx1 = min(200,i+4);
int nx2 = min(200,i+3);
f[i] = p * (i/200.0+(1-i/200.0)*(f[nx1]+1))
+ (1-p) * (f[nx2] + 1);
}
printf("Case %d: %.10f\n",++ cc,f[4]);
}
}
E
推公式数学题。解方程。直接套求根公式比魔改求根公式的精度要高（？）
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN=1e3+10;
const int mod=1e9+7;
const double eps=1e-7;
int sgn(double a){
if (fabs(a)<eps) return 0;
if (a>0) return 1;
return -1;
}
int main(){
int T,cas=0; scanf("%d",&T);
while(T--){
double r,h;
scanf("%lf%lf",&r,&h);
double ppx,ppy,ppz,ddx,ddy,ddz;
scanf("%lf%lf%lf",&ppx,&ppy,&ppz);
scanf("%lf%lf%lf",&ddx,&ddy,&ddz);
long double px=ppx,py=ppy,pz=ppz,dx=ddx,dy=ddy,dz=ddz;
long double ox=px,oy=py,oz=pz;
long double k = r*r/h/h;
long double a = dx * dx + dy * dy - k * dz * dz;
long double b = 2 * (dx * ox + dy * oy - k * dz * (oz - h));
long double c = ox * ox + oy * oy - k * (oz - h) * (oz - h);
long double discrim = b * b - 4 * a * c;
long double rootDiscrim = sqrt(discrim);
/*long double q;
if (b < 0) q = (-b + rootDiscrim)/2;
else q = (-b - rootDiscrim)/2;
long double t0 = q / a;
long double t1 = c / q;
long double ans=min(t0,t1);
if(ans < 1e-8) ans = 0;*/
long double ans = (-b-rootDiscrim)/2/a;
printf("Case %d: %.10f\n",++cas,(double)ans);
}
return 0;
}
F
因为左端点递增，所以 i 包含 k 那么 j 一定包含 k，所以 j 取 i-1 最优，每个点的答案就是 x-2。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int SZ = 2e5 + 10;
const int mod = 1e9+7;
LL read() {
LL n = 0;
char a = getchar();
bool flag = 0;
while(a > '9' || a < '0') { if(a=='-') flag = 1; a = getchar(); }
while(a <= '9' && a >= '0') { n=n*10+a-'0'; a = getchar(); }
if(flag) n=-n;
return n;
}
int main() {
int T = read(),cc = 0;
while(T --) {
int n = read(),ans = 0;
for(int i = 1;i <= n;i ++) {
int x = read();
x = max(x-2,0);
ans ^= x;
}
printf("Case %d: %d\n",++ cc,ans);
}
}
G
题意：给 \(10^4\) 个一欧姆的电阻。定义一个元件：
一个一欧姆电阻是一个元件
两个元件并联是一个元件
两个元件串联是一个元件
构造一个元件，使得其电阻阻值与 \(r\) 的绝对值之差小于 \(10^{-7}\)
key：随机，乱搞
有连分数做法，不过不太会……
众所周知 n 个 a 欧姆的电阻并联的电阻是 a/n。想要得到一个尽量小的电阻那么一定是若干个一欧姆电阻并联。
考虑把 r 拆分成若干个 1/ki，这其实是埃及分数。我们的目标是使得 \(\sum k_i \le 10^4\) 。
考虑加入一个 1/ki，那么能算出 ki 的下界。每次选下界的贪心是不优的，而我们只需要找到一个较优解。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
int T,cc = 0;
scanf("%d",&T);
while(T --) {
int n;
scanf("%d",&n);
int ans = 0;
for(int i = 1,r;i <= n;i = r + 1) {
r = n / (n / i);
ans += (r-i+1ll) * (n / i) & 1;
}
if(ans&1) printf("Case %d: odd\n",++ cc);
else printf("Case %d: even\n",++ cc);
}
}
B
基础模拟。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
int T,cc = 0;
scanf("%d",&T);
map<string,int> mp;
mp["Beijing"] = 8;
mp["Washington"] = -5;
mp["London"] = 0;
mp["Moscow"] = 3;
while(T --) {
int h,m;
string s,name1,name2;
scanf("%d:%d",&h,&m);
cin >> s >> name1 >> name2;
h %= 12;
if(s == "PM") h += 12;
int delta = mp[name2] - mp[name1];
h += delta;
//cout << h << endl;
string rq;
if(h >= 24) rq = "Tomorrow";
else if(h < 0) rq = "Yesterday";
else rq = "Today";
h += 24; h %= 24;
string ans;
if(h <= 11) ans = "AM";
else ans = "PM",h -= 12;
if(h == 0) h = 12;
printf("Case %d: %s %d:%02d %s\n",++ cc,rq.c_str(),h,m,ans.c_str());
}
}
C
基础贪心。也可以写并查集。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int SZ = 2e5 + 10;
int bel[SZ],tot,sum,mark[SZ];
vector<int> g[SZ];
void dfs(int u,int c) {
bel[u] = c;
for(int v : g[u]) {
dfs(v,c);
}
}
int main() {
int T,cc = 0;
scanf("%d",&T);
while(T --) {
int n;
scanf("%d",&n);
for(int i = 1;i <= tot;i ++) {
bel[i] = 0;
mark[i] = 0;
g[i].clear();
}
tot = n,sum = 0;
priority_queue<pii> q;
for(int i = 1;i <= n;i ++) {
int x;
scanf("%d",&x);
q.push(make_pair(x,i));
}
while(q.size()) {
pii p = q.top(); q.pop();
if(p.first <= 1) { mark[p.second] = 1; sum ++; continue; }
if(q.size()) {
pii p2 = q.top(); q.pop();
if(p2.first == p.first) {
pii ans = make_pair(p.first-1,++ tot);
//printf("%d -> %d\n",tot,p.second);
// printf("%d -> %d\n",tot,p2.second);
g[tot].push_back(p.second);
g[tot].push_back(p2.second);
q.push(ans);
}
else q.push(p2);
}
}
if(sum < 2) {
printf("Case %d: NO\n",++ cc);
}
else {
printf("Case %d: YES\n",++ cc);
int t = 0;
for(int i = 1;i <= tot;i ++) {
if(mark[i]) {
dfs(i,t);
if(t==0) t++;
}
}
for(int i = 1;i <= n;i ++) printf("%d",bel[i]); puts("");
}
}
}
D
基础概率DP。由于会加1.5%所以状态要乘2。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int SZ = 2e5 + 10;
double f[333];
int main() {
int T,cc = 0;
scanf("%d",&T);
while(T --) {
int pp;
scanf("%d",&pp);
double p = 1.0*pp/100;
f[200] = 1/p;
for(int i = 199;i >= 4;i --) {
int nx1 = min(200,i+4);
int nx2 = min(200,i+3);
f[i] = p * (i/200.0+(1-i/200.0)*(f[nx1]+1))
+ (1-p) * (f[nx2] + 1);
}
printf("Case %d: %.10f\n",++ cc,f[4]);
}
}
E
推公式数学题。解方程。直接套求根公式比魔改求根公式的精度要高（？）
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN=1e3+10;
const int mod=1e9+7;
const double eps=1e-7;
int sgn(double a){
if (fabs(a)<eps) return 0;
if (a>0) return 1;
return -1;
}
int main(){
int T,cas=0; scanf("%d",&T);
while(T--){
double r,h;
scanf("%lf%lf",&r,&h);
double ppx,ppy,ppz,ddx,ddy,ddz;
scanf("%lf%lf%lf",&ppx,&ppy,&ppz);
scanf("%lf%lf%lf",&ddx,&ddy,&ddz);
long double px=ppx,py=ppy,pz=ppz,dx=ddx,dy=ddy,dz=ddz;
long double ox=px,oy=py,oz=pz;
long double k = r*r/h/h;
long double a = dx * dx + dy * dy - k * dz * dz;
long double b = 2 * (dx * ox + dy * oy - k * dz * (oz - h));
long double c = ox * ox + oy * oy - k * (oz - h) * (oz - h);
long double discrim = b * b - 4 * a * c;
long double rootDiscrim = sqrt(discrim);
/*long double q;
if (b < 0) q = (-b + rootDiscrim)/2;
else q = (-b - rootDiscrim)/2;
long double t0 = q / a;
long double t1 = c / q;
long double ans=min(t0,t1);
if(ans < 1e-8) ans = 0;*/
long double ans = (-b-rootDiscrim)/2/a;
printf("Case %d: %.10f\n",++cas,(double)ans);
}
return 0;
}
F
因为左端点递增，所以 i 包含 k 那么 j 一定包含 k，所以 j 取 i-1 最优，每个点的答案就是 x-2。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int SZ = 2e5 + 10;
const int mod = 1e9+7;
LL read() {
LL n = 0;
char a = getchar();
bool flag = 0;
while(a > '9' || a < '0') { if(a=='-') flag = 1; a = getchar(); }
while(a <= '9' && a >= '0') { n=n*10+a-'0'; a = getchar(); }
if(flag) n=-n;
return n;
}
int main() {
int T = read(),cc = 0;
while(T --) {
int n = read(),ans = 0;
for(int i = 1;i <= n;i ++) {
int x = read();
x = max(x-2,0);
ans ^= x;
}
printf("Case %d: %d\n",++ cc,ans);
}
}
G
题意：给 \(10^4\) 个一欧姆的电阻。定义一个元件：
一个一欧姆电阻是一个元件
两个元件并联是一个元件
两个元件串联是一个元件
构造一个元件，使得其电阻阻值与 \(r\) 的绝对值之差小于 \(10^{-7}\)
key：随机，乱搞
有连分数做法，不过不太会……
众所周知 n 个 a 欧姆的电阻并联的电阻是 a/n。想要得到一个尽量小的电阻那么一定是若干个一欧姆电阻并联。
考虑把 r 拆分成若干个 1/ki，这其实是埃及分数。我们的目标是使得 \(\sum k_i \le 10^4\) 。
考虑加入一个 1/ki，那么能算出 ki 的下界。每次选下界的贪心是不优的，而我们只需要找到一个较优解。
