亿些代码
zl0244
·
·
个人记录
合并果子(AC)
//合并果子
//数组优化
#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, l, x, y, a[100005], b[100005], p, q, ans;
int main(){
scanf("%d", &n);
memset(a, 127, sizeof(a));
memset(b, 127, sizeof(b));
for(i=1; i<=n; i++){
scanf("%d", &a[i]);
}
sort(a+1, a+1+n);
x=1,y=n,p=q=1;
for(i=1; i<n; i++){
if(a[x+1] < b[p]){
b[q++]=a[x+1] + a[x];
x += 2;
}
else if(b[p+1] < a[x]){
b[q++]=b[p] + b[p+1];
p += 2;
}
else{
b[q++]=a[x] + b[p];
x++, p++;
}
ans += b[q-1];
}
printf("%d", ans);
return 0;
}
//队列
#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, l,x,y,ans;
priority_queue <int> q;
int main(){
scanf("%d", &n);
for(i=1; i<=n; i++){
int k;
scanf("%d", &k);
q.push(-k);
}
for(i=1; i<n; i++){
int o=q.top();
q.pop();
int p=q.top();
q.pop();
ans += o + p;
q.push(o+p);
}
printf("%d",-ans);
return 0;
}
//普通找最大最小
#include <stdio.h>
int n, m, i, j, k, l,x,y,ans, a[100005];
int main(){
scanf("%d", &n);
for(i=1; i<=n; i++){
scanf("%d", &a[i]);
}
a[0]=2e9;
for(i=1; i<n; i++){
x=y=0;
for(j=1; j<=n; j++){
if(a[j] <= a[x]){
y=x, x=j;
}
else if(a[j] < a[y]){
y=j;
}
}
ans = ans + a[x] + a[y];
a[x]=a[y]+a[x];
a[y]=a[0];
}
printf("%d",ans);
return 0;
}
棋盘
// 深
// 搜
//#include <bits/stdc++.h>
//using namespace std;
//int n, m, i, j, k, xx, yy, ans, s;
//int f[1005][1005][2], mp[1005][1005];
//const int dx[]={0, 1, 0, -1}, dy[]={1, 0, -1, 0};
//void dfs(int x, int y, int z, int s){
// int xx, yy, zz;
// if(x<1 || x>n || y<1 || y>n) return ;
// if(s >= f[x][y][z]) return;//最优性剪枝。
// if(s >= f[n][n][0]||s >= f[n][n][1]) return;
// f[x][y][z] = s;
// for(int i=0; i<4; ++i){
// xx = x+dx[i], yy = y+dy[i], zz=mp[xx][yy];
// if(zz == -1){
// if(z == mp[x][y]) dfs(xx, yy, z, s+2);
// else continue;
// }
// else dfs(xx, yy, zz, s+(zz!=z));
// }
//}
//int main(){
// scanf("%d%d", &n, &m);
// memset(mp, -1, sizeof(mp));//赋初值。
// memset(f, 9, sizeof(f));
// for(i=1; i<=m; i++){
// int a, b, c;
// scanf("%d%d%d", &a, &b, &c);
// mp[a][b] = c;
// }
// dfs(1, 1, mp[1][1], 0);
// ans = f[n][n][0] < f[n][n][1] ? f[n][n][0] : f[n][n][1];
// printf("%d", ans!=f[0][0][0] ? ans : -1);
// return 0;
//}
// 广
// 搜
//#include <bits/stdc++.h>
//#define N 11
//#define Nm 127
//#define M 4
//#define Mm 15
//using namespace std;
//int n, m, i, j, k, x, y, z, v, xx, yy, zz, ans, s;
//int mp[1005][1005], f[1005][1005][2], q[20000005];
//const int dx[4]={0, 0, 1, -1}, dy[4]={1, -1, 0, 0};
//int main(){
// scanf("%d%d", &n, &m);
// memset(mp, -1, sizeof(mp));
// memset(f, 9, sizeof(f));
// for(i=1; i<=m; ++i){
// int x, y, z;
// scanf("%d%d%d", &x, &y, &z);
// mp[x][y]=z;
// }
// f[1][1][mp[1][1]]=0, q[1]=1<<N|1<<M|mp[1][1];
// for(i=j=1; i<=j; ++i){
// x = q[i]>>N, y = q[i]>> M & Nm, z = q[i] & Mm, v = f[x][y][z];
//// printf("Q=%d xyz=%d %d %d v=%d\n", q[i], x, y, z, v);
// for(k=0; k<4; ++k){
// xx = x+dx[k], yy = y+dy[k], zz=mp[xx][yy];
// if(xx<1 || xx>n || yy<1 || yy>n) continue;
// if(zz == -1){
// if(z == mp[x][y]) v = f[x][y][zz=z] + 2;
// else v = f[0][0][0];
// }
// else v = f[x][y][z] + (zz != z);
// if(v < f[xx][yy][zz]){
// f[xx][yy][zz] = v, q[++j] = xx<<N | yy<<M | zz;
// }
// }
// }
// ans = f[n][n][0] < f[n][n][1] ? f[n][n][0] : f[n][n][1];
// printf("%d", ans!=f[0][0][0] ? ans : -1);
// return 0;
//}
// 迪
// 杰
// 斯
// 特
// 拉
#include <bits/stdc++.h>
#define N 11
#define Nm 127
#define M 4
#define Mm 15
using namespace std;
int n, m, i, j, k, x, y, z, v, xx, yy, zz, ans, s;
int mp[1005][1005], f[1005][1005][2], q[20000005];
const int dx[4]={0, 0, 1, -1}, dy[4]={1, -1, 0, 0};
void zhaozihao(int &x, int &y, int &z){
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(!u[x][y][1] && )
if(!u[x][y][0] && )
}
}
u[x][y][z] = 1;
}
int main(){
scanf("%d%d", &n, &m);
memset(mp, -1, sizeof(mp));
memset(f, 9, sizeof(f));
for(i=1; i<=m; ++i){
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
mp[x][y]=z;
}
for(i=1; i<=n; i++){
zhaozihao(x=0, y=0, z=0);
for(xx=1; k<=n; k++){
for(yy){
}
}
}
ans = f[n][n][0] < f[n][n][1] ? f[n][n][0] : f[n][n][1];
printf("%d", ans!=f[0][0][0] ? ans : -1);
return 0;
}
/*
5 7
1 1 0
1 2 0
2 2 1
3 3 1
3 4 0
4 4 1
5 5 0
*/
万年历
#include <bits/stdc++.h>
using namespace std;
#define qiqian 114514
#define qi 1919
#define qian 810
#define ll long long
int n, m, i, j, k, h, p, q, l, t;
int offset = 6, yuey[15], ok[100005];
int ji[15] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int dayNum[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int main() {
scanf("%d", &m);
if(m%4==0 && m%100!=0 || m%400==0) dayNum[2]++;
if(m < 2000){
for(i=1999; i>=m; i--){
if(i%4==0 && i%100!=0 || i%400==0) offset = (offset + 371 - 366)%7;
else offset = (offset + 371 - 365)%7;
}
}
else if(m > 2000){
for(i=2000; i<m; i++){
if(i%4==0 && i%100!=0 || i%400==0) offset = (offset + 366)%7;
else offset = (offset + 365)%7;
}
}
printf(" %d \n\n", m);
for(i=1; i<=12; i++){
offset = (offset + dayNum[i-1])%7;
yuey[i] = offset;
}
for(j=1; j<=4; j++){
l = (j-1)*3;
if(j == 1) printf(" January February March \n");
else if(j == 2) printf(" April May June \n");
else if(j == 3) printf(" July August September \n");
else if(j == 4) printf(" October November December \n");
printf("Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa\n");
for(q=1; q<=6; q++){
for(h=l+1; h<=l+3; h++){
if(ji[h] > dayNum[h]){
printf(" ");
continue;
}
if(q == 1){
for(i=1; i<=yuey[h]; i++){
printf(" ");
}
}
for(i=ji[h]; i<ji[h]+7, i<=dayNum[h]; i++){
if(i<10) printf(" %d ", i);
else printf("%d ", i);
if(i == dayNum[h]){
for(t=ji[h]+6; t>i; t--){
printf(" ");
}
break;
}
if((yuey[h] + i) % 7 == 0) break;
}
ji[h] = i+1;
printf(" ");
}
printf("\n");
}
}
return 0;
}
//1900.1.1是周一
//(x+365)是7的倍数+今年第一天是周几 、
// x = offset+7a-365
大整数(WA)
#include <bits/stdc++.h>
#define N 99
using namespace std;
int i, j, k, x[N], y[N], z[N];
int n[N], m[N], l[N], r[N], t[N], s[N], san[N]={1, 3};
char o[N];
void chu2(int *a){
for(i=a[0]; i>1; i--){
if(a[i]&1) a[i-1] += 10;
a[i] >>= 1;
}
a[i] /= 2;
while(a[0] > 1 && !a[a[0]]) a[0]--;
}
void jia(int *a, int *b){
memset(t, 0, sizeof(t));
t[0] = max(a[0], b[0]);
for(i=1; i<=t[0]; i++){
t[i] += a[i] + b[i];
if(t[i] > 9) t[i] -= 10, t[i+1] = 1;
}
if(t[i]) t[0]++;
memcpy(a, t, sizeof(t));
}
void cheng(int *s, int *a, int *b){
memset(s, 0, sizeof(t));
for(i=1; i<=a[0]; i++){
for(j=1; j<=b[0]; j++){
s[i] += a[i] * b[j];
}
}
s[0] = a[0] + b[0] - 1;
for(i=1; i<=s[0]||s[i]; i++){
s[i+1] += s[i] / 10;
s[i] %= 10;
}
s[0] = i - 1;
}
void jian(int *a){
a[i=1]--;
while(a[i] < 0) a[i++] += 10, a[i]--;
if(i == a[0]){
while(a[0]>1 && !a[a[0]]) a[0]--;
}
}
int sda(){
if(s[0] != n[0]) return s[0] > n[0];
for(i=s[0]; i>=1; i--){
if(s[i] != n[i]) return s[i] > n[i];
}
return 0;
}
void out(int *a){
for(i=a[0]; i>=1; i--) printf("%d", a[i]);
printf("\n");
}
int main(){
// int x[N]={1, 3, 3}, y[N]={2, 0, 1};
scanf("%s", o+1);
n[0] = strlen(o+1);
for(i=1; i<=n[0]; i++) n[i] = o[n[0]+1-i] - 48;
l[0] = r[30] = 1, r[0] = 30;
// for(i=1; i<=30; i++) r[i] = 1;
while(memcmp(l, r, r[0]*4+4) != 0){
memset(m, 0, sizeof(m));
m[0] = m[1] = 1;
jia(m, l);
jia(m, r);
chu2(m);
// out(m);
cheng(x, m, san);
cheng(y, m, m);
cheng(z, y, m);
// out(m)
memset(s, 0, sizeof(s));
jia(s, x);
jia(s, y);
jia(s, z);
// k = m*m*m + m*m + 3*m;
if(sda()){
jian(m);
memcpy(r, m, sizeof(m));
}
else memcpy(l, m, sizeof(m));
}
// return memcmp(l, r, r[0]*4) == 0;
out(r);
return 0;
}
//1000000000000001000000000000003000000000000001
}
幻灯片(AC)
//广搜
#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, kk, a[105], b[105];
int r[105], q[105], h[105], f[105], mp[105][105], ans[105];
struct JB{
int x1, x3, y1, y3;
} d[105];
int main(){
scanf("%d", &n);
for(i=1; i<=n; i++){
scanf("%d%d%d%d", &d[i].x1, &d[i].x3, &d[i].y1, &d[i].y3);
}
for(i=1; i<=n; i++){
scanf("%d%d", &a[i], &b[i]);
}
for(i=1; i<=n; i++){
for(j=1; j<=n; j++){
mp[i][j] = (a[i] <= d[j].x3 && a[i] >= d[j].x1 && b[i] <= d[j].y3 && b[i] >= d[j].y1);
r[i] += mp[i][j];
}
}
q[1] = m = 1;
for(i=1; i<=m; i++){
int a = q[i];//点
// if(r[a] != 1) continue;
r[a]--;
for(j=1; j<=n; j++){//幻灯片
if(mp[a][j]){
ans[j] = a, mp[a][j] = 0;
for(k=1; k<=n; k++){
if(mp[k][j]){
mp[k][j] = 0;
r[k]--;
if(r[k] == 1) q[++m] = k;
}
}
}
}
}
// if(m < n){
// printf("None\n");
// return 0;
// }
for(i=1; i<=n; i++) printf("%c %d\n", char('A'+i-1), ans[i]);
return 0;
}
//深搜
#include<bits/stdc++.h>
using namespace std;
struct JB{
int x1, x3, y1, y3;
} d[30];
struct dick{
int x, y;
} p[30];
int n, m, i, j, k, pd;
int mp[30][30], u[30], ans[30];//mp记录点与幻灯片的关系，u记录点的边数，ans记录答案
void find(int k){
int i, j;
pd++, u[k]--;
for(i=1; i<=n; i++){//找相对应的点与幻灯片
if(!mp[k][i]) continue;
ans[i] = k, mp[k][i] = 0;//ans记录答案，清边
for(j=1; j<=n; j++){//清除幻灯片与其它点的边
if(mp[j][i]){
u[j]--;
mp[j][i] = 0;
if(u[j] == 1) find(j);//如果清边后有且只有一条边，查找它
}
}
break;
}
}
int main(){
scanf("%d", &n);
for(i=1; i<=n; i++){//读入幻灯片坐标
scanf("%d%d%d%d", &d[i].x1, &d[i].x3, &d[i].y1, &d[i].y3);
}
for(i=1; i<=n; i++){//点的坐标
scanf("%d%d", &p[i].x, &p[i].y);
for(j=1; j<=n;j++){//判断点与幻灯片的关系
if(p[i].x <= d[j].x3 && p[i].x >= d[j].x1 && p[i].y <= d[j].y3 && p[i].y >= d[j].y1){
mp[i][j] = 1, u[i]++;//建边
}
}
}
for(i=1; i<=n; i++){
if(u[i] == 1) find(i);//判断相连的点与幻灯片是否唯一
}
if(pd < n){
printf("None\n");
return 0;
}
for(i=1; i<=n; i++){
char shit = char('A'+i-1);
printf("%c %d\n", shit, ans[i]);
}
return 0;
}
差分约束C题(未改好)
#include <bits/stdc++.h>
using namespace std;
int m, n, i, j=1, k, kk, a, b, c, l;
int f[30005], h[30005], u[30005], q[1000005];
struct JB{
int a, b, c, n;
// bool operator < (const JB &A) const {
// return c < A.c;
// }
} d[200005];
void cun(int a, int b, int c){
d[++kk] = {a, b, c, h[a]}, h[a] = kk;
}
int main(){
scanf("%d%d", &l, &n);
for(i=1; i<=n; i++){
int a, b, c;
scanf("%d%d%d", &c, &a, &b);
if(c == 1){ cun(a, b, 0); cun(b, a, 0);}//<= >=
if(c == 2){ cun(a, b, 1);}//<
if(c == 3){ cun(b, a, 0);}//>=
if(c == 4){ cun(b, a, 1);}//>
if(c == 5){ cun(a, b, 0);}//<=
}
// memset(f, -1, sizeof(f));
// for(j=1; j<=l; j++){
// cun(j, j+1, 0);
// cun(j, j-1, f[j]=-1);
// q[j]=j, u[j]=1;
// }
//for(i=1; i<=n; i++){
// printf("%d ", h[i]);
//}
//cout << endl;
memset(f, 9, sizeof(f));
f[1] = 0, q[1] = u[1] = 1;
for(i=j=1; i<=j; i++){
// cout << 123;
int a = q[i]; u[a] = 0;
// cout << endl << h[a] << endl;
for(int k=h[a]; k; k=d[k].n){
// cout << 123;
int b = d[k].b, c = d[k].c;
// if(c == 1) f[b] = f[a];
// if(c == 2) f[b] = f[a]+1;
// if(c == 3) f[b] = f[a]-1;
// if(c == 4) f[b] = f[a]-1;
// if(c == 5) f[b] = f[a]+1;
// cout << f[a] << endl;
if(f[a]+c < f[b]){
// cout << i << " " << k << " ";
f[b] = f[a] + c;
if(!u[b]){
u[b] = 1;
q[++j] = b;
}
}
}
}
printf("%d\n", f[l]);
return 0;
}
重力球(WA50)
#include <bits/stdc++.h>
using namespace std;
int n, m, ans, a, b, c, d, o, ji, p[33][33], f[33][33][33][33], q[810005];
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
void zhaozihao(int &x, int &y, int i){
while(!p[x][y]){
x += dx[i], y += dy[i];
}
x -= dx[i], y -= dy[i];
}
void bfs(int x, int y, int xx, int yy){
q[1] = x<<15|y<<10|xx<<5|yy, f[x][y][xx][yy] = 0;
int i, j, s, t, ss, tt;
for(i=j=1; i<=j; i++){
x = q[i]>>15, y = q[i]>>10&31, xx = q[i]>>5&31, yy = q[i]&31;
for(int k=0; k<4; k++){
zhaozihao(s=x, t=y, k);
zhaozihao(ss=xx, tt=yy, k);
if(s == ss && t == tt){
ans = f[x][y][xx][yy] + 1;
return;
}
if(f[x][y][xx][yy] + 1 < f[s][t][ss][tt]){
f[s][t][ss][tt] = f[x][y][xx][yy] + 1;
q[++j] = s<<15|t<<10|ss<<5|tt;
}
}
}
ji = j;
}
void jb(){
int dx, dy;
for(long long j=1; j<=ji; j++){
dx = (q[j]>>10), dy = (q[j]&1023);
f[dx>>5][dx&31][dy>>5][dy&31] = f[0][0][0][0];
}
ji = 0;
}
int main() {
scanf("%d%d%d", &n, &m, &o);
// mem();
memset(f, 9, sizeof(f));
for(int i=1; i<=m; i++){
int a, b;
scanf("%d%d", &a, &b);
p[a][b] = 1;
}
for(int i=1; i<=n; ++i) p[0][i] = p[n+1][i] = p[i][0] = p[i][n+1] = 1;
for(int x, y, xx, yy, i=1; i<=o; ++i){
scanf("%d%d%d%d", &x, &y, &xx, &yy);
if(x==xx&&y==yy){
printf("0\n");
continue;
}
ans = 1e9;
bfs(x, y, xx, yy);
if(ans>=1e9-1) printf("-1\n");
else printf("%d\n", ans);
// mem();
jb();
}
return 0;
}
/*
4 4 3
2 2
2 4
3 2
4 4
1 3 4 3
2 1 2 1
1 2 3 4
*/
/*
#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, p, ans, q[255][255], f[11005][11005];
long long ji, jj[100005];
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
int zhaozihao(int x, int y, int i){
int xx = x, yy = y;
while(!q[xx][yy]){
xx += dx[i], yy += dy[i];
}
xx -= dx[i], yy -= dy[i];
return xx<<5|yy;
}
void dfs(int x, int y, int xx, int yy, int bushu){
int dx, dy, i;
if(xx == x && yy == y){
ans = min(ans, bushu);
return ;
}
if(bushu >= ans) return ;
if(bushu >= f[x<<5|y][xx<<5|yy]) return ;
else f[x<<5|y][xx<<5|yy] = bushu;
// printf("(%d %d)\n", x<<5|y, xx<<5|yy);
jj[++ji] = x << 15 | y << 10 | xx << 5 | yy;
for(i=0; i<4; i++){
dx = zhaozihao(x, y, i);
dy = zhaozihao(xx, yy, i);
dfs(dx>>5, dx&31, dy>>5, dy&31, bushu+1);
}
}
//void mem(){
// int i, j;
// for(i=1; i<=1005; ++i){
// for(j=1; j<=1005; ++j){
// f[i][j] = 1e9;
// }
// }
//}
int main() {
scanf("%d%d%d", &n, &m, &p);
// mem();
memset(f, 9, sizeof(f));
for(i=1; i<=n; i++) {
int a, b;
scanf("%d%d", &a, &b);
q[a][b] = 1;
}
for(i=1; i<=n; ++i){
q[0][i] = q[n+1][i] = q[i][0] = q[i][n+1] = 1;
}
for(i=1; i<=p; ++i){
int x, y, xx, yy;
scanf("%d%d%d%d", &x, &y, &xx, &yy);
ans = 1e9;
dfs(x, y, xx, yy, 0);
if(ans == 1e9) printf("-1\n");
else printf("%d\n", ans);
// mem();
for(long long j=1; j<=ji; j++){
int dx = (jj[j]>>10);
int dy = (jj[j]&1023);
f[dx][dy] = f[0][0];
}
ji = 0;
}
return 0;
}
*/
无名代码unknown
#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k;
int w[100005], v[100005], f[1005][1005];
int dfs(int k, int s){
int i, p, q=1e9;
if(k > n) return 0;
if(s > m) return 1e9;
if(f[k][s] != f[0][0]) return f[k][s];
for(i=0; i<=m/v[k]; i++){
// printf("v = %d, %d\n", v[k], m/v[k]);
p = dfs(k+1, s+v[k]*i) + w[k]*i;
q = q>p ? p:q;
}
return f[k][s] = q;
}
int main(){//可以填物品编号
scanf("%d%d", &m, &n);
for(i=1; i<=n; i++){
scanf("%d%d", &w[i], &v[i]);
}
memset(f, -1, sizeof(f));
printf("%d\n", dfs(1, 0));
return 0;
}
/*
*/
#include <bits/stdc++.h>
#define max(a,b) a>b?a:b
#define lowbit(a) a&-a
using namespace std;
int n, m, i, j, k, ans1, ans2;
int cnt[200005], q[200005], f[200005], d[200005];
void xia(int lc, int rc, int p){//修正下放
if(d[lc] == d[rc]) cnt[p] = cnt[lc] + cnt[rc], d[p] = d[lc];
else if(d[rc] > d[lc]) cnt[p] = cnt[rc], d[p] = d[rc];
else cnt[p] = cnt[lc], d[p] = d[lc];
}
void jia(int p, int l, int r, int k, int z){//单点修改
if(l == r) d[p] = z, cnt[p]=1;//找到坐标，单点修改，记录相同的最大值的树当期区间变为1
else{
int m=l+r>>1, lc=p<<1, rc=p<<1|1;//找
if(k <= m) jia(lc, l, m, k, z);
if(k > m) jia(rc, m+1, r, k, z);
xia(lc, rc, p);
}
}
void cha(int p, int l, int r, int x, int y){//区间查询最大值
if(x<=l && r<=y){//包括区间l r：记录答案
if(ans1 < d[p]) ans1 = d[p], ans2 = cnt[p];
// if(ans1 == d[p]) ans2 += cnt[p];
}
else{
int m=l+r>>1, lc=p<<1, rc=p<<1|1;//找
if(x <= m) cha(lc, l, m, x, y);
if(y > m) cha(rc, m+1, r, x, y);
xia(lc, rc, p);
}
}
int main(){
scanf("%d%d", &n, &m);
for(i=1; i<=n; i++){
int b;
scanf("%d", &b);
cnt[i]=1;//赋初值
jia(1, 1, n, i, b);
}
for(i=1; i<=m; i++){
char s[15];
int a, b;
scanf("%s%d%d%*c", s+1, &a, &b);
if(s[1] == 'C'){//更新
jia(1, 1, n, a, b);
for(j=1; j<=n; j++) printf("(%d %d) ", d[j], cnt[i]);
printf("\n");
}
else{//查询
ans1=-1, ans2=-1;
cha(1, 1, n, a, b);
for(j=1; j<=n; j++) printf("(%d %d) ", d[j], cnt[i]);
printf("\n");
printf("%d %d\n", ans1, ans2);
}
}
}
/*
5 3
2 4 3 6 8
Ask 1 5
Change 2 10
Ask 1 3
*/
#include <bits/stdc++.h>
#define max(a,b) a>b?a:b
#define lowbit(a) a&-a
using namespace std;
int n, m, i, j, k, ans=-1;
int cnt[200005], q[200005], f[200005], d[200005];
int pd(int k){
for(int i=2; i*i<=n; i++) if(k%i==0) return 0;
return 1;
}
int gcd(int a, int b){
if(a%b==0) return b;
return gcd(b, a%b);
}
int fk(int n){
int i, j, k;
for(i=3; i<=n; i++){
if(pd(i)){
for(j=i; j<=n; j+=i){
f[j]++;
}
}
if(sn) return i;
}
return -1;
}
int main(){
scanf("%d", &n);
printf("%d", fk(n));
}
#include <stdio.h>
#include <string.h>
#define N 1005
int n, m, i, j, k, a[N], f[N][N], ans;
int he(int x, int y){
for(int i=x+1, s=a[x]; i<=y; i++){
s=s*10+a[i];
}
return s;
}
int dfs(int k, int s){
int i, p, q=0;
if(k == n) return 0;
if(s > m) return -1e9;
if(f[k][s]!=f[0][0]) return f[k][s];
for(i=1; i<=n; i++){
}
return
}
int main(){
scanf("%d%d", &n, &m);
m = n-m;
for(i=1; i<=n; i++){
scanf("%1d", &a[i]);
}
memset(f, -1, sizeof(f));
printf("%d\n", dfs(1,0));
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, ans=1e9;
int u[105][105], s[1005];
int dfs(int l, int r){
int q=1e9, p;
if(r-l<=2) return 0;
if(u[l][r] != u[0][0]) return u[l][r];
for(int i=l; i<r; i++){
p = dfs(l, i)+dfs(i+1, r)+s[l]*s[r]*s[i];
if(p < q) q = p;
}
return u[l][r] = q;
}
int main(){
scanf("%d", &n);
for(i=1; i<=n; i++){
scanf("%d", &s[i]);
s[i+n] = s[i];
}
for(i=1; i<=n; i++) ans = min(ans, dfs(i, i+n-1));
printf("%d", ans);
exit(0);
}
/*
5
121 122 123 245 231
12214884
*/
}
#include <bits/stdc++.h>
using namespace std;
#define N 1005
int n, m, i=1, c, j, k;
int a[N], f[N][N], ans;
char s[N];
int main(void){
scanf("%s", s+1);
n = strlen(s+1);
for(i=1; i<=n; i=-~i)f[i][i] = 1;
for(c=2; c<=n; c=-~c){
for(i=1; i+c<=n; i++, j++){
j = i+c;
f[i][j] = 1e9;
for(int k=i;k<j;k++) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
if((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']')) f[i][j]=min(f[i][j],f[i+1][j-1]);
}
}
printf("%d", f[1][n]);
}
//#include <stdio.h>
//#include <string.h>
//#define N 1005
//int n, m, i=1, j, k;
//int a[N], s[5], u[N][N], ans;
//char c[N];
//int pei(int l, int r){
// if(a[l] == 1&&a[r] == 2) return 1;
// if(a[l] == 3&&a[r] == 4) return 1;
// return 0;
//}
//int dfs(int l, int r){
// int i, q=0, p;
// if(l == r) return 0;
// if(pei(l, r)) q = dfs(l+1, r-1) + 2;
//// if(u[l][r] != u[0][0]) return u[l][r];
// for(i=l; i<r; i++){
// p = dfs(l, i) + dfs(i+1, r);
// if(p > q) q = p;
// }
// return u[l][r] = q;
//}
//int main(){
// while(scanf("%c", &c[i]) == 1){
// i=-~i;
// a[i] = c[i]=='('? 1:a[i];
// a[i] = c[i]==')'? 2:a[i];
// a[i] = c[i]=='['? 3:a[i];
// a[i] = c[i]==']'? 4:a[i];
// s[a[i]]++;
// }
// i = i-dfs(1, i)*2;
// memset(u, -1, sizeof(u));
// printf("%d\n", i);
// return 0;
//}
///*
//[])
//*/
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
char s[205], w[9][25], f[205][205];
int i, j, k, n, m, c;
int shu(int k, int i){
return ;
}
int main(){
scanf("%d %d", &c, &m);
for(i=0; i<c; i++){
scanf("%s", s+1+i*20);
}
n = strlen(s+1);
scanf("%d", &c);
for(i=1; i<=c; i++){
scanf("%s", w[i]);
}
for(i=1; i<=n; i++){
for(j=1; j<=min(i, m); j++){
for(k=j; k<=i; k++){
f[i][j]=max(f[i][j], f[k-1][j-1]+shu(k, i));
}
}
}
printf("%d", f[n][m]);
return 0;
}
/*
1 3
thisisabookyouareaoh
4
is
a
ok
sab
*/
GDKOI
day1a
#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, jb[5], shit, ax, ay, ai, aj, a[2005][2005];
int main(){
scanf("%d", &n);
for(i=1; i<=n; i++){
for(j=1; j<=n; j++){
scanf("%d", &a[i][j]);
}
}
jb[1] = a[1][n], jb[2] = a[n][1];
for(i=2; i<=n; i++){
jb[1] ^= a[i][n];
jb[2] ^= a[n][i];
}
for(i=2; i<n; i++){
shit = a[i][2];
for(j=3; j<=n; j++) shit ^= a[i][j];
shit ^= jb[1];
if(shit!= a[i][1]) ax = i, ai++;
}
for(i=2; i<n; i++){
shit = a[2][i];
for(j=3; j<=n; j++) shit ^= a[j][i];
shit ^= jb[2];
if(shit!= a[1][i]) ay = i, aj++;
}
if(ai == 1&&aj == 1) printf("%d %d", ax, ay);
else if(ai == 1 && !aj) printf("%d %d", ax, 1);
else if(ai == 1 && aj>1) printf("%d %d", ax, n);
else if(!ai && aj == 1) printf("%d %d", 1, ay);
else if(ai > 1 && aj == 1) printf("%d %d", n, ay);
else if(!ai && !aj) printf("%d %d", 1, 1);
else if(ai > 1 && aj > 1) printf("%d %d", n, n);
else if(!ai && aj > 1) printf("%d %d", 1, n);
else if(ai > 1 && !aj) printf("%d %d", n, 1);
return 0;
}
day1b
#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k;
long long s[200005], d[200005], a[200005], p, l, r;
int main(){
scanf("%d%d", &n, &m);
a[0] = d[0] = a[n+1] = 1e9, p = sqrt(n), d[(n+1)/p] = 1e9;
for(i=1; i<=n; i++){
scanf("%lld", &a[i]);
d[i/p] = max(d[i/p], a[i]);
s[i] = s[i-1] + a[i];
}
while(m--){
scanf("%d%d", &i, &k);
for(l=i-1; a[l]<k; l--){
if((l+1)%p==0 && d[l/p]<k) l -= p-1;
}
for(r=i+1; a[r]<k; r++){
if(r%p==0 && d[r/p]<k) r += p-1;
}
printf("%lld\n", k*(r-1-l)-s[r-1]+s[l]);
}
return 0;
}
day1c
#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, l, r, ans, a[1000005];
int main(){
scanf("%d%d%d", &n, &l, &r);
for(i=1; i<=n; i++)scanf ("%d", &a[i]);
sort(a+1, a+n+1);
for(i=1, j=n; i<=j; ){
if(i == j) ans++, i++;
else{
if(a[i]+a[j] > r) j--, ans++;
else if(a[i]+a[j] < l) i++, ans++;
else i++, j--;
}
}
printf("%d", ans);
return 0;
}
day1d
#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, q, a, b, c, f[200005], g[200005];
void jb{
int a, b, c, i;
} d[2000005], s[200005];
bool cmp1 (JB a, JB b){
return a.c < b.c;
}
bool cmp2 (JB a, JB b){
return a.i < b.i;
}
int find(int x){
if(x == f[x]) return x;
return f[x] = find(f[x]);
}
int main(){
scanf("%d%d", &n, &m);
for(i=1; i<=m; i++) scanf("%d%d%d", &d[i].a, &d[i].b, &d[i].c);
scanf("%d", &q);
sort(d+1, d+m+1, cmp1);
for(i=1; i<=q; i++){
scanf("%d%d", &s[i].a, &s[i].c);
s[i].i = i;
}
sort(s+1, s+q+1, cmp1);
for(i=1; i<=n; i++) f[i] = i, g[i] = 1;
for(i=j=1; i<=m; i++){
a = d[i].a, b = d[i].b, c = d[i].c;
while(j <= q&&c > s[j].c) {
s[j].b = g[find(s[j].a)], j++;
}
}
return 0;
}
...
#include <bits/stdc++.h>
#include <time.h>
using namespace std;
int i, j, k, kk, a, b, c, z, n, m, ans;
void jia(int i, int x){
while (i <= n){
c[i] += x;
i += -i&i;
}
}
int he(int i){
int s = 0;
while(i){
s += c[i];
i -= -i&i;
}
return s;
}
int main(){
scanf("%d%d", &n, &m);
for(i=1; i<=n; i++){
scanf("%d", &a[i]);
jia(i, a[i]);
}
for(i=1; i<=m; i++){
scanf("%d%d%d", &k, &x, &y);
if(k == 1){
jia(x, y-a[x]);
a[x] = y;
}
else{
printf("%d\n", he(y)-he(x-1));
}
}
return 0;
}