Lemon_kk

1.3万

class Solution {
public:
vector<bool> st;
vector<int> path;
int n;

bool dfs(int u){
if(u >= 2 * n - 1) return true;
if(path[u]) return dfs(u + 1);
for(int i = n;i > 1;i -- ){
if(st[i] || i + u >= 2 * n - 1 || path[u + i]) continue;
st[i] = true;
path[u] = path[u + i] = i;
if(dfs(u + 1)) return true;
st[i] = false;
path[u] = path[u + i] = 0;
}
if(!st[1]){
st[1] = true;
path[u] = 1;
if(dfs(u + 1)) return true;
st[1] = false;
path[u] = 0;
}

return false;
}
vector<int> constructDistancedSequence(int _n) {
n = _n;
st.resize(n + 1, false);
path.resize(n * 2 - 1, 0);
dfs(0);
return path;
}
};


### 贪心找最大 可以过小样例

class Solution {
public:
int maximumGain(string s, int x, int y) {
int res = 0;
if(x < y){
swap(x, y);
for(auto &c : s)
if(c == 'a') c = 'b';
else if(c == 'b') c = 'a';
}
string last = "";
while(true){
for(int i = 0;i + 1 < s.size();i ++ ){
if(s[i] != 'a' && s[i] != 'b') continue;
int j = i + 1;
while(j < s.size() && s[j] == 'A') j ++ ;
if(s[i] == 'a' && s[j] == 'b'){
res += x;
s[i] = 'A';
s[j] = 'A';
}
}
if(last == s) break;
last = s;
}

while(true){
for(int i = 0;i + 1 < s.size();i ++ ){
if(s[i] != 'a' && s[i] != 'b') continue;
int j = i + 1;
while(j < s.size() && s[j] == 'A') j ++ ;
if(s[i] == 'b' && s[j] == 'a'){
res += y;
s[i] = 'A';
s[j] = 'A';
}
}
if(last == s) break;
last = s;
}

return res;
}
};


### 正解

class Solution {
public:
int maximumGain(string s, int x, int y) {
int res = 0;
if(x < y){
swap(x, y);
for(auto &c : s)
if(c == 'a') c = 'b';
else if(c == 'b') c = 'a';
}
for(int i = 0;i < s.size();i ++ ){
if(s[i] != 'a' && s[i] != 'b') continue;
int j = i;
while(j < s.size() && (s[j] == 'a' || s[j] == 'b')) j ++ ;
int a = 0, b = 0, c = 0;
for(int k = j - 1, t = 0;k >= i;k -- ){
if(s[k] == 'a'){
a ++ ;
if(t){
t -- ;
c ++ ;
}
}else if(s[k] == 'b'){
b ++ ;
t ++ ;
}
}
res += c * x + y * (min(a, b) - c);
i = j - 1;
}

return res;
}
};


class Solution {
public:
int totalMoney(int n) {
int sum = 0, last = 0, now = 0;
for(int i = 1;i <= n;i ++ ){
if(i % 7 == 1) last ++ , now = last;
sum += now ++ ;
}
return sum;
}
};


### 选取中位数求和

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N];

int main(){
scanf("%d", &n);
for(int i = 1;i <= n;i ++ ) scanf("%d", &a[i]);
sort(a + 1, a + 1 + n);
int ans = 0;
for(int i = 1;i <= n;i ++ ){
ans += abs(a[i] - a[1 + n / 2]);
}

cout << ans << endl;
return 0;
}


## 拓展：二维的欧式距离最短

### 第一种：三分套三分

根据dist = sum(sqrt(dx * dx + dy * dy));
dist 对 x 的二阶偏导大于零 所以是凹函数



#include <cmath>
#include <cstdio>
#include <cstring>

#define INF double(1e10)

using namespace std;

const int N = 150;

int n, x[N], y[N];
double dist = INF;
double eps = 1e-3;
double lx, rx, ly, ry;

double get_dist(double xx, double yy){
double res = 0;
for (int i = 1; i <= n; ++i) {
double dx = x[i] - xx, dy = y[i] - yy;
res += sqrt(dx * dx + dy * dy);
}
return res;
}

double f(double x){
ly = 0, ry = 10010;
while(ry - ly > eps){
double lmid = (ly + ry) / 2;
double rmid = (lmid + ry) / 2;
if(get_dist(x, lmid) < get_dist(x, rmid)) ry = rmid;
else ly = lmid;
}
dist = min(dist, get_dist(x, ly));
return ly;
}

int main() {

scanf("%d", &n);
for (int i = 1;i <= n;i ++ ) scanf("%d%d", &x[i], &y[i]);

lx = 0, rx = 10010;
while(rx - lx > eps){
double lmid = (lx + rx) / 2;
double rmid = (lmid + rx) / 2;
if(get_dist(lmid, f(lmid)) < get_dist(rmid, f(rmid))) rx = rmid;
else lx = lmid;
}

printf("%.lf\n", dist);

return 0;
}


### 第二种：模拟退火

#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>

using namespace std;

const int N = 150;

int n, x[N], y[N];
double ansx, ansy, dist;

double Rand() { return (double)rand() / RAND_MAX; }
double get_dist(double xx, double yy){
double res = 0;
for (int i = 1; i <= n; ++i) {
double dx = x[i] - xx, dy = y[i] - yy;
res += sqrt(dx * dx + dy * dy);
}
// if(res < dist) dist = res, ansx = xx, ansy = yy;
return res;
}

void simulateAnneal(){
double T = 1e5; // 初始温度要足够大
double eps = 1e-6; // 结束温度足够低
double down = 0.99; // 降温时间足够长
double nowx = ansx, nowy = ansy;
while(T > eps){
// 随机 计算数值
double nxtx = nowx + T * (Rand() * 2 - 1);
double nxty = nowy + T * (Rand() * 2 - 1);
double delta = get_dist(nxtx, nxty) - get_dist(nowx, nowy);
if(delta < 0) nowx = nxtx, nowy = nxty, dist = dist + delta;
T *= down;
}

ansx = nowx, ansy = nowy;
for (int i = 1; i <= 1000; ++i) {
double nxtx = ansx + T * (Rand() * 2 - 1);
double nxty = ansy + T * (Rand() * 2 - 1);
double z = get_dist(nxtx, nxty);
if(z < dist) dist = z, ansx = nxtx, ansy = nxty;
}
}
int main() {

srand(time(0));
scanf("%d", &n);

for (int i = 1; i <= n; ++i) {
scanf("%d%d", &x[i], &y[i]);
ansx += x[i], ansy += y[i];
}
// 初始化 初解
ansx /= n, ansy /= n, dist = get_dist(ansx, ansy);
// 模拟退火
simulateAnneal();
// printf("%.3lf %.3lf\n", ansx, ansy);
printf("%.lf\n", get_dist(ansx, ansy));

return 0;
}


#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N];

int main(){
scanf("%d", &n);
for(int i = 1;i <= n;i ++ ) scanf("%d", &a[i]);
sort(a + 1, a + 1 + n);
int ans = 0;
for(int i = 1;i <= n;i ++ ){
ans += abs(a[i] - a[1 + n / 2]);
}

cout << ans << endl;
return 0;
}


Lemon_kk
18天前
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 45;

LL n, L, I;
LL c[N][N];
LL f[N][N];

int main(){

cin >> n >> L >> I;
for(int i = 0;i < N;i ++ )
for(int j = 0;j <= i;j ++ )
if(!j) c[i][j] = 1;
else c[i][j] = c[i - 1][j - 1] + c[i - 1][j];

for(int i = 0;i < N;i ++ )
for(int j = 0;j < N;j ++ )
for(int k = 0;k <= j;k ++ )
f[i][j] += c[i][k];

LL sum = 0;
for(int i = 1;i <= n;i ++ ){
LL x = f[n - i][L - sum];
if(x >= I){
cout << 0;
}else{
I -= x;
cout << 1;
sum ++ ;
}
}
return 0;
}


Lemon_kk
29天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010, M = 1 << 14;

int A, B, n, m;
int cnt[M];
struct Data{
int k, val;
bool operator<(const Data& t)const{
if(k != t.k) return k > t.k;
return val < t.val;
}
string get_string(){
string res;
for(int i = val;i;i >>= 1) res += (i & 1) + '0';
res.pop_back();
reverse(res.begin(), res.end());
return res;
}
}q[N];

int main(){
string line, str;
cin >> A >> B >> m;
while(cin >> line) str += line;
n = str.size();

for(int i = A;i <= B;i ++ ){
for(int j = 0, num = 0;j < n;j ++ ){
num = num * 2 + str[j] - '0';
if(j - i >= 0) num -= str[j - i] - '0' << i;
if(j + 1 >= i) cnt[num + (1 << i)] ++ ;
}
}

for(int i = 0;i < M;i ++ )
q[i] = {cnt[i], i};

sort(q, q + M);

for(int i = 0, cnt = 0;i < M && cnt < m;cnt ++ ){
if(!q[i].k) break;
int j = i;
while(j < M && q[j].k == q[i].k) j ++ ;
cout << q[i].k << endl;
for(int a = i, b = 1;a < j;a ++ , b ++ ){
cout << q[a].get_string();
if(b % 6 == 0) cout << endl;
else cout << ' ';
}
if((j - i) % 6) cout << endl;
i = j;
}

return 0;
}


Lemon_kk
29天前
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 100, K = 210, M = 2000010;

int k, n, m;
int f[M];

int main(){
scanf("%d%d", &k, &n);
memset(f, 0x3f, sizeof f);
f[0] = 0;
m = M - 1;
for(int i = 1;i <= n;i ++ ){
int x; cin >> x;
for(int j = x;j <= m;j ++ )
f[j] = min(f[j], f[j - x] + 1);
}

int t = 0;
while(f[t] <= k) t ++ ;
cout << t - 1 << endl;

return 0;
}


Lemon_kk
29天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010, M = 110;
const LL INF = 1e17;

int n, k;
int p[N], q[N];
vector<LL> res;

int main(){

scanf("%d%d", &n, &k);
for(int i = 1;i <= n;i ++ ) scanf("%d", &p[i]);

res.push_back(1);
for(int i = 1;i <= k;i ++ ){
LL t = INF;
for(int j = 1;j <= n;j ++ )
t = min(t, res[q[j]] * p[j]);
for(int j = 1;j <= n;j ++ )
if(res[q[j]] * p[j] == t)
q[j] ++ ;
res.push_back(t);
}

cout << res.back() << endl;

return 0;
}


Lemon_kk
29天前
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e4 + 10;

int n, m;
int p, t;
int f[N];

int main(){

scanf("%d%d", &m, &n);
for(int i = 1;i <= n;i ++ ){
cin >> p >> t;
for(int j = t;j <= m;j ++ )
f[j] = max(f[j], f[j - t] + p);
}

cout << f[m] << endl;

return 0;
}