A题:
思路:
简单模拟即可注意LL。
代码:
#include <iostream>
using namespace std;
constexpr int N = 1e5 + 10;
using LL = long long;
int n;
int a[N];
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i ++)
{
scanf("%d",&a[i]);
while(a[i] > 0 && (a[i]%2 == 0))a[i] >>= 1;
}
LL res = 0;
for(int i = 0; i < n; i ++)res += (LL)a[i];
printf("%lld\n",res);
return 0;
}
B题:
思路:
1e18的复杂度->二分做法。
关键在于check函数怎么写:
手玩发现以这样一种方案放置最优:
因为ans >= [n/2]向上取整,故先在左侧从上往下放ans个1 * [n/2],
接着填充右上角的长方形需要(ans - [n/2]) / 1个。
最后是右下角填充1 * 1的正方形也需要(ans - [n/2]) / 1个。
因此在假设边长为ans的情况下需要3 * ans - [n/2](上取整)*2 个积木。
接着用二分即可。
代码:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
using LL = long long;
constexpr int N = 1e4;
bool check(LL ans, LL n)
{
LL num = 0;
num += ans;
num += ans - (n + 1 >> 1);
num += ans - (n + 1 >> 1);
if (num <= n)return true;
else return false;
}
int main()
{
int T;
cin >> T;
while (T -- )
{
LL x;
cin >> x;
if(x == 2ll)
{
cout << "-1\n";
continue;
}
LL l = 0ll, r = x;
while(l < r)
{
LL mid = l + r + 1>> 1;
if (check(mid, x))l = mid;
else r = mid - 1;
}
cout << r << '\n';
}
return 0;
}
C题:
思路:
构造数列,发现4是有解的,如果长度为8我们就让序列为:[3 4 1 2 7 8 5 6],
由此发现可以令4为一个模块,模块与模块之间是不影响的仅加了4而已,
接下来就要处理模块长度%4不为0的情况。
这里看了jls大佬的代码理解他的过程是:
如果%4的余数不为0,则做给一次%4=1的模块使得总长度变为(n - 5);
这样原本%4 = x的余数x就会减一,一直重复这个过程直到剩余的长度n’%4=0为止,
之后可以直接安排n/4个长度为4的模块。
可能是之前没做过这种构造题,感觉不太好写。
代码:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using LL = long long;
constexpr int N = 1e4;
int main()
{
int n;
cin >> n;
vector<int>a(n);
if (n == 7 || n < 4)
{
cout << -1 << '\n';
return 0;
}
else
{
int i = 0;
if (n == 6)
{
cout << "4 5 6 1 2 3";
return 0;
}
if (n == 11)
{
cout << "3 4 1 6 2 8 5 10 11 7 9";
return 0;
}
while( (n - i) % 4 != 0)
{
a[i + 0] = i + 4;
a[i + 1] = i + 5;
a[i + 2] = i + 1;
a[i + 3] = i + 2;
a[i + 4] = i + 3;
i += 5;
}
while(i < n)
{
a[i + 0] = i + 3;
a[i + 1] = i + 4;
a[i + 2] = i + 1;
a[i + 3] = i + 2;
i += 4;
}
for(int i = 0; i < n; i++)cout << a[i] << " ";
}
return 0;
}
D题:
思路:
手玩前10个找规律,注意n <= 1e18.用long long
代码:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using LL = long long;
constexpr int N = 1e4;
int main()
{
LL n;
cin >> n;
if (n&1ll)cout << "yukari\n";
else cout << "kou\n";
return 0;
}
E题:
思路:
用向量,关键在于二倍坐标系避免判断小数(新学到的)。
代码:
版本一(自己写的答辩double判是否是整点)
比赛的时候一直少考虑一种情况,一直以为两个点的性质是一样的,但其实可能c是整点而d不是整点。
所以要两个都试一试才行。
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
constexpr int N = 1e5 + 10;
using LL = long long;
int n;
int a[N];
bool final = false;
bool sol(double x, double y)
{
bool flag = true;
if (fabs(x - round(x)) > 1e-3)flag = false;
if (fabs(y - round(y)) > 1e-3)flag = false;
if (flag)return true;
else return false;
}
int main()
{
double x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
double mx, my, k;
mx = (x1 + x2) / 2;
my = (y1 + y2) / 2;
k = (y1 - y2) / (x1 - x2);
// cout << "k is " << k << '\n';
double resx, resy;
if (k <= 0)
{
resx = mx + fabs(y1 - my);
resy = my + fabs(x1 - mx);
if (sol(resx,resy))
{
cout << (LL)resx << " " << (LL)resy;
return 0;
}
resx = mx - fabs(y1 - my);
resy = my - fabs(x1 - mx);
if (sol(resx,resy))
{
cout << (LL)resx << " " << (LL)resy;
return 0;
}
cout << "No Answer!";
}
else
{
resx = mx + fabs(y1 - my);
resy = my - fabs(x1 - mx);
if (sol(resx,resy))
{
cout << (LL)resx << " " << (LL)resy;
return 0;
}
resx = mx - fabs(y1 - my);
resy = my + fabs(x1 - mx);
if (sol(resx,resy))
{
cout << (LL)resx << " " << (LL)resy;
return 0;
}
cout << "No Answer!";
}
return 0;
}
版本二
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using LL = long long;
constexpr int N = 1e4;
int main()
{
LL xa, ya, xb, yb;
cin >> xa >> ya >> xb >> yb;
//如果在原坐标系下求AB中点可能会出现小数,将x和y同乘2之后避免了这种情况发生
xa <<= 1;xb <<= 1;ya <<= 1; yb <<= 1;
LL mx = xa + xb >> 1;
LL my = ya + yb >> 1;
LL dx = mx - xa;
LL dy = my - ya;
//status 1
if ((mx + dy)%2 == 0 && (my - dx)%2 == 0)
{
cout << (mx + dy) / 2 << " " << (my - dx) / 2 << "\n";
}
else if ( (mx - dy)%2 == 0 && (my + dx)%2 == 0 )
{
cout << (mx - dy) / 2 << " " << (my + dx) / 2 << "\n";
}
else cout << "No Answer!\n";
return 0;
}
F题:
思路:
输出42。
代码:
#include <iostream>
using namespace std;
int main()
{
cout << 42 << '\n';
return 0;
}
I题:
思路:
素数筛 + 哥德巴赫猜想 + 公式推导。
代码:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using LL = long long;
constexpr int N = 1e6 + 10;
int primes[N], cnt;
bool st[N];
void getp(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i])primes[cnt ++] = i;
for(int j = 0; primes[j] <= n / i; j ++)
{
st[primes[j] * i] = true;
if (i % primes[j] == 0)break;
}
}
}
void sol(int x)
{
if (x <= 7)
{
int ans[] = {0,-1,-1,4,9,-1,25,8};
cout << ans[x] << "\n";
return ;
}
if (x%2 == 0)
{
if (!st[x - 1])cout << (LL)(x - 1)*(x - 1) << '\n';
else cout << 2 * (x - 3) << '\n';
return ;
}
else
{
int tem = 0;
while(st[x - 1 - primes[tem]])tem ++;
cout << (LL)primes[tem] * (x - 1 - primes[tem]) << '\n';
return ;
}
}
int main()
{
int n, x;
cin >> n;
getp(int(1e6));
for (int i = 0; i < n; i ++ )
{
cin >> x;
sol(x);
}
return 0;
}
补充:
因子数公式:f(x) = a^i * b^j * c^k...;
其中a,b,c...均为质数,i,j,k...为指数
那么x的因子数 = (i + 1)*(j + 1)*(k + 1)...以此类推