Day 2
T1
赛时想的爆了，只能去拿40pts暴力
正解是统计质因子个数，然后二分答案判断每个质因子能否满足
但是可以只判2的个数，或者为了确保其不背卡常使用数十个质数即可。
#include <bits/stdc++.h>
#define ll long long
#define gt getchar
#define pt putchar
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=gt();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
return x*f;}
inline void print(ll x){if(x<0)pt('-'),x=-x;if(x>9)print(x/10);pt(x%10+48);}
void file(){freopen("a.in", "r", stdin);freopen("a.out", "w", stdout);}
int n, m;
int a[200005];
int t, res;
int get(int x)
{
int ans = 0;
while(x)ans += x / 2, x /= 2;
return ans;
}
int main()
{
file();
n = read(), m = read();
for(int i = 1; i <= m; ++ i)a[i] = read();
sort(a + 1, a + m + 1);
t = get(n);
for(int i = 1; i <= m; ++ i)
{
if((res += get(a[i])) > t)
{
cout << i - 1;
return 0;
}
}
cout << m;
return 0;
}
T2
赛时的dp写完了之后第二个大样例没过去，因为少判了多段不交合并的情况
改一改就行了
#include <bits/stdc++.h>
#define ll long long
#define gt getchar
#define pt putchar
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=gt();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
return x*f;}
inline void print(ll x){if(x<0)pt('-'),x=-x;if(x>9)print(x/10);pt(x%10+48);}
void file(){freopen("b.in", "r", stdin);freopen("b.out", "w", stdout);}
int n, k;
int a[505], val[505];
int f[505][505];
int main()
{
//file();
n = read(), k = read();
for(int i = 1; i <= n; ++ i)a[i] = read(), val[i] = val[i - 1] ^ a[i];
for(int l = n - 1; l; -- l)for(int r = l + 1; r <= n; ++ r){
f[l][r] = 1 << 30;
for(int g = r; g > l; g -= k - 1)f[l][r] = min(f[l][r], f[l][g - 1] + f[g][r]);
if((r - l) % (k - 1) == 0)f[l][r] += val[r] ^ val[l - 1];
}
cout << f[1][n];
return 0;
}