头像

silver.bullet


访客:2855

离线:1天前


活动打卡代码 AcWing 330. 估算

define MAXN 2011

define MAXK 27

ll f[MAXK][MAXN],a[MAXN],cost[MAXN][MAXN],suml=0,sumr=0;//前面三个如上所述,suml表示左边大根堆中元素的和,sumr表示右边小根堆中元素的和
std::priority_queue[HTML_REMOVED]q1;
std::priority_queue[HTML_REMOVED],std::greater[HTML_REMOVED] >q2;//对顶堆
void clear()//清空对顶堆
{
std::priority_queue[HTML_REMOVED]tmp1;
std::priority_queue[HTML_REMOVED],std::greater[HTML_REMOVED] >tmp2;
q1.swap(tmp1),q2.swap(tmp2);
suml=sumr=0;
}
void push(ll val)//插入元素val
{
if(q1.empty())q1.push(val),suml+=val;//插入大根堆还是小根堆
else if(val>q1.top())q2.push(val),sumr+=val;
else q1.push(val),suml+=val;
while(q1.size()>q2.size()+1)//调整两个堆中的元素数量直至q2.size()<=q1.size()<=q2.size()+1
{
sumr+=q1.top();
q2.push(q1.top());
suml-=q1.top();
q1.pop();
}
while(q1.size()<q2.size())
{
suml+=q2.top();
q1.push(q2.top());
sumr-=q2.top();
q2.pop();
}
}
int main()
{
while(1)
{
ll n=read(),k=read();
if(!n&&!k)break;
for(ll i=1;i<=n;i)a[i]=read();
for(ll i=1;i<=n;
i)//预处理cost
{
clear();
for(ll j=i;j<=n;j)
{
push(a[j]);
ll val=q1.top();
cost[i][j]=valq1.size()-suml;
if(!q2.empty())cost[i][j]+=sumr-val
q2.size();
}
}
memset(f,0x3f,sizeof f);
f[0][0]=0;
for(ll i=1;i<=k;
i)//dp
for(ll j=1;j<=n;j)
for(ll pre=0;pre<j;
pre)
umin(f[i][j],f[i-1][pre]+cost[pre+1][j]);
printf(“%lld\n”,f[k][n]);
}
return 0;
}




include[HTML_REMOVED]

using namespace std;
typedef long long ll;
const int maxn = 3e4+10;
const int base = 1e5+1;
const int m = base*2;
int n, s;
int l[maxn], r[maxn];
ll f[maxn][2];

struct SegmentTree
{
int l, r;
int id;
int laz;
#define lson (p<<1)
#define rson (p<<1|1)
#define l(x) tree[x].l
#define r(x) tree[x].r
#define id(x) tree[x].id
#define laz(x) tree[x].laz
}tree[m<<2];

void spread(int p)
{
if(laz(p))
{
laz(lson) = laz(rson) = 1;
id(lson) = id(rson) = id(p);
laz(p) = 0;
}
}

void build(int p, int l, int r)
{
l(p) = l, r(p) = r;
if(l == r) return;
int mid = (l+r)>>1;
build(lson, l, mid); build(rson, mid+1, r);
}

int ask(int p, int x)
{
if(l(p) == r(p)) return id(p);
int mid = (l(p)+r(p))>>1;
spread(p);
if(x <= mid) return ask(lson, x);
else return ask(rson, x);
}

void change(int p, int L, int R, int v)
{
if(L <= l(p) && r(p) <= R) {
id(p) = v;
laz(p) = 1;
return;
}
spread(p);
int mid = (l(p)+r(p))>>1;
if(L <= mid) change(lson, L, R, v);
if(mid < R) change(rson, L, R, v);
}

int main()
{
scanf(“%d%d”, &n, &s);
s += base;
build(1, 1, m);
//直接走回原点
l[0] = r[0] = base;
for(int i = 1; i <= n; i++)
{
scanf(“%d%d”, &l[i], &r[i]);
l[i] += base; r[i] += base;
int lv = ask(1, l[i]);
int rv = ask(1, r[i]);
f[i][0] = min(f[lv][0]+abs(l[lv]-l[i]), f[lv][1]+abs(r[lv]-l[i]));
f[i][1] = min(f[rv][0]+abs(l[rv]-r[i]), f[rv][1]+abs(r[rv]-r[i]));
change(1, l[i], r[i], i);
}

int ans = min(f[n][0]+abs(l[n]-s), f[n][1]+abs(r[n]-s));
cout << ans << endl;
return 0;

}



活动打卡代码 AcWing 328. 芯片

include[HTML_REMOVED]

using namespace std;
const int Max_N=150,Max_M=10,Max_S=61e4;
int N,M,K,Pow[12]={},Last[Max_M+10]={},Now[Max_M+10]={},Cut[Max_N+10][Max_M+10]={},F[2][Max_S+10]={};
inline int Tr_Te(int
A){
int Ans=0;
for(int i=1;i<=M;i) Ans+=A[i]Pow[i-1];
return Ans;
}
inline void Te_Tr(int x,int
A){
for(int i=1;i<=M;i
) A[i]=x%3,x/=3;
}
inline void dfs(int x,int Id,int Max,int S){
F[Id][S]=max(F[Id][S],Max);
if(x>M) return;
dfs(x+1,Id,Max,S);
if(x+1<=M&&Last[x]==0&&Last[x+1]==0&&Now[x]==0&&Now[x+1]==0){
Now[x]=Now[x+1]=2;
dfs(x+2,Id,Max+1,Tr_Te(Now));
Now[x]=Now[x+1]=0;
}
if(x+2<=M&&Now[x]==0&&Now[x+1]==0&&Now[x+2]==0){
Now[x]=Now[x+1]=Now[x+2]=2;
dfs(x+3,Id,Max+1,Tr_Te(Now));
Now[x]=Now[x+1]=Now[x+2]=0;
}
}
inline void Work(){
scanf(“%d%d%d”,&N,&M,&K);
for(int i=1;i<=K;i){
int x,y; scanf(“%d%d”,&x,&y);
Cut[x][y];
}
Pow[0]=1;
for(int i=1;i<=M;i) Pow[i]=Pow[i-1]*3;
for(int i=1;i<=M;i
) Last[i]=Cut[1][i]?2:1;
memset(F[1],-10,sizeof(F[1]));
int S=Tr_Te(Last); F[1][S]=0;
for(int i=2;i<=N;i){
memset(F[i%2],-10,sizeof(F[i%2]));
for(int j=0;j<Pow[M];j
){
if(F[(i-1)%2][j]<0) continue;
Te_Tr(j,Last);
for(int k=1;k<=M;k) Now[k]=Cut[i][k]?2:(Last[k]?Last[k]-1:0);
dfs(1,i%2,F[(i-1)%2][j],Tr_Te(Now));
}
}
int Ans=0;
for(int i=0;i<Pow[M];i
) Ans=max(Ans,F[N%2][i]);
printf(“%d\n”,Ans);
}
int main(){
int T; scanf(“%d”,&T);
for(;T–;){
memset(Cut,0,sizeof(Cut));
Work();
}
return 0;
}



活动打卡代码 AcWing 327. 玉米田

include [HTML_REMOVED]

using namespace std;
const int P=1e9;
int a[15][15],f[15],h[5010],dp[15][5010],ans;
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i)
for(int j=1;j<=m;j
){
cin>>a[i][j];
f[i]=(f[i]<<1)+a[i][j];
}
dp[0][0]=1;
for(int i=0;i<(1<[HTML_REMOVED]>1))==0);
for(int i=1;i<=n;i)
for(int j=0;j<(1<<m);j
)
if(h[j]&&((f[i]&j)==j))
for(int k=0;k<(1<<m);k)
if((j&k)==0)dp[i][j]=(dp[i][j]+dp[i-1][k])%P;
for(int i=0;i<(1<<m);i
)ans=(ans+dp[n][i])%P;
cout<<ans;
return 0;
}




include [HTML_REMOVED]

typedef long long ll;
int a[20], m[20], n;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
ll d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}

ll CRT() {
ll ans = 0;
ll M = 1;
ll t1, t2;
for (int i = 1; i <= n; i) M *= m[i];
for (int i = 1; i <= n; i
) {
ll Mi = M / m[i];
exgcd(Mi, m[i], t1, t2);
ans = (ans + a[i] * Mi % M * t1) % M;
}
return (ans + M) % M; //保证结果为正整数
}
int main() {
scanf(“%d”, &n);
for (int i = 1; i <= n; i++) {
scanf(“%d%d”, m + i, a + i);
}
printf(“%lld”, CRT());
return 0;
}



活动打卡代码 AcWing 339. 圆形数字

/
Name: rndnum
Author: silver bullet
Date: 30/07/20 19:27
/

include[HTML_REMOVED]

using namespace std;

inline int read() {
int X = 0, w = 0;
char ch = 0;
while (!isdigit(ch)) {
w |= ch == ‘-‘;
ch = getchar();
}
while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
return w ? -X : X;
}

int f[35][35], d[35], q;
int ps(int i, int x) {
if (i == 0 || x > i) return 34;
if (x < -i) return 0;
if (i % 2 == 0) {
if (x % 2 == 0) return i / 2 + x / 2;
return i / 2 + x / 2 + ((x > 0) ? (1) : (0));
} else {
if (x % 2 == 0) return i / 2 + 1 + (x - 1) / 2 + ((x - 1 > 0) ? (1) : (0));
return i / 2 + 1 + (x - 1) / 2;
}
}
int solve(int x) {
if(x <= 1) return 0;
int ans = q = 0, c = 1;
while (x) {
d[++q] = x % 2;
x >>= 1;
}
for (int i = q - 2; i >= 1; i–) ans += f[i][ps(i, 1)];
for (int i = q - 1; i >= 1; i–) {
if(d[i] == 1) {
c–;
ans += f[i-1][ps(i - 1, c)];
c += 2;
} else
c–;
}
return ans + (c <= 0) + (d[1] == 1 && c - 2 <= 0);
}

int main() {
memset(f, 0, sizeof f);
for (int i = 1; i <= 32; i) {
f[i][0] = 1;
f[i][1] = i;
f[i][i] = 1;
for (int j = 2; j < i; j
) f[i][j] = f[i][j - 1] * (i - (j - 1)) / j;
for (int j = i - 1; j >= 0; j–) f[i][j] += f[i][j + 1];
}
int a = read(), b = read();
printf(“%d”, solve(b) - solve(a-1));
puts(“”);
return 0;
}



活动打卡代码 AcWing 406. 放置机器人

include[HTML_REMOVED]

using namespace std;

const int MAXN = 1e4;
const int maxn = 1e5 + 10;
const int maxm = 2e6 + 10;
const int inf = 0x3f3f3f3f;

int n, m, a[55][55], b[55][55];
char mp[55][55];
struct EDGE {
int to, flow, next;
} edge[maxm];

inline int read()
{
int X=0,w=0; char ch=0;
while(!isdigit(ch)) {w|=ch==’-‘;ch=getchar();}
while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
return w?-X:X;
}

struct ios_out {
template [HTML_REMOVED]
inline void operator << (_Tp &x) {
char F[MAXN];
_Tp tmp = x > 0 ? x : (putchar(‘-‘), -x);
int cnt = 0;
while (tmp) {
F[cnt++] = tmp % 10 + ‘0’;
tmp /= 10;
}
while (cnt) putchar(F[–cnt]);
}
} Cout;

class Grape {
private:
int num, head[maxn], depth[maxn], cur[maxn];
public:
int s, t;
void init() {
num = 2;
memset(head, 0, sizeof(head));
}
void add_e(int x, int y, int flow) {
edge[num] = (EDGE){y, flow, head[x]};
head[x] = num;
}
void add(int x, int y, int flow) {
add_e(x, y, flow);
add_e(y, x, 0);
}
int dfs(int x, int flow) {
if (x == t)
return flow;
for (int &i = cur[x]; i; i = edge[i].next) {
int to = edge[i].to;
int f = edge[i].flow;
if (depth[to] == depth[x] + 1 and f != 0) {
int w = dfs(to, min(flow, f));
if (w > 0) {
edge[i].flow -= w;
edge[i ^ 1].flow += w;
return w;
}
}
}
return 0;
}
int bfs() {
queue[HTML_REMOVED] Q;
memset(depth, 0, sizeof(depth));
depth[s] = 1;
Q.push(s);
do {
int x = Q.front();
Q.pop();
for (int i = head[x]; i; i = edge[i].next) {
int to = edge[i].to;
int flow = edge[i].flow;
if (depth[to] == 0 and flow > 0) {
depth[to] = depth[x] + 1;
Q.push(to);
}
}
} while (Q.size());
if (depth[t] > 0)
return 1;
return 0;
}
int dinic() {
int ans = 0;
while (bfs()) {
for (int i = s; i <= t; i
)
cur[i] = head[i];
while (int f = dfs(s, inf))
ans += f;
}
return ans;
}
} dinic;

int main() {

ifndef ONLINE_JUDGE

freopen("test.in","r",stdin);

endif

int t=read();
for(int T = 1; T <= t; T++) {
    n=read(),m=read();
    dinic.init();
    memset(a, 0, sizeof a);
    memset(b, 0, sizeof b);
    dinic.s = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin>>mp[i][j];
    int num = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(mp[i][j] == '#') continue;
            if(j == 1) num++;
            else if(mp[i][j-1] == '#') num++;
            a[i][j] = num;

        }
    }
    for(int i = 1; i <= num; i++)
        dinic.add(0, i, 1);
    int start = num;

    for(int j = 1; j <= m; j++) {
        for(int i = 1; i <= n; i++) {
            if(mp[i][j] == '#') continue;
            if(i == 1) num++;
            else if(mp[i-1][j] == '#') num++;
            b[i][j] = num;
        }
    }
    for(int i = start + 1; i <= num; i++)
        dinic.add(i, num+1, 1);

    dinic.s = 0;
    dinic.t = num+1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(mp[i][j] == 'o')
                dinic.add(a[i][j], b[i][j], 1);
    cout<<"Case :";
    Cout <<T;
    puts("");
    cout<< dinic.dinic();
    puts("");
}
return 0;

}



活动打卡代码 AcWing 164. 可达性统计

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
const int maxx=5005002;
char mp[505][505];
int k1[505][505],k2[505][505];
int n,m;
struct node{
int to;
int next;
}e[maxx];
int k,head[maxx];
void add(int u,int v){
e[k].to=v;
e[k].next=head[u];
head[u]=k;
}
int match[maxx],vis[2500],cnt1,cnt2;
void build(){
for(int i=1;i<=n;i
){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
}
}

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(mp[i][j]=='*'){
            if(mp[i][j-1]=='*'){
                k1[i][j]=cnt1;
            }
            else{
                cnt1++;
                k1[i][j]=cnt1;  
            }

        }
    }
}

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
            if(mp[i][j]=='*'){
            if(mp[i-1][j]=='*'){
                k2[i][j]=k2[i-1][j];
            }
            else{
                cnt2++;
                k2[i][j]=cnt2;  
            }
        }
    }
}

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        add(k1[i][j],k2[i][j]+n*m);
    }
}

}
int dfs(int u){
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(!vis[v]){
vis[v]=1;
if(!match[v]||dfs(match[v])){
match[u]=v;
match[v]=u;
return 1;
}
}
}
return 0;
}
void debug(){
for(int i=1;i<=n;i){
for(int j=1;j<=m;j
){
cout<[HTML_REMOVED]>n>>m;
build();
// debug();
for(int i=1;i<=cnt1;i){
if(!match[i]){
memset(vis,0,sizeof(vis));
if(dfs(i)) sum
;
}
}
cout<<sum<<endl;
}



活动打卡代码 AcWing 377. 泥泞的区域

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
const int maxx=5005002;
char mp[505][505];
int k1[505][505],k2[505][505];
int n,m;
struct node{
int to;
int next;
}e[maxx];
int k,head[maxx];
void add(int u,int v){
e[k].to=v;
e[k].next=head[u];
head[u]=k;
}
int match[maxx],vis[2500],cnt1,cnt2;
void build(){
for(int i=1;i<=n;i
){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
}
}

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(mp[i][j]=='*'){
            if(mp[i][j-1]=='*'){
                k1[i][j]=cnt1;
            }
            else{
                cnt1++;
                k1[i][j]=cnt1;  
            }

        }
    }
}

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
            if(mp[i][j]=='*'){
            if(mp[i-1][j]=='*'){
                k2[i][j]=k2[i-1][j];
            }
            else{
                cnt2++;
                k2[i][j]=cnt2;  
            }
        }
    }
}

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        add(k1[i][j],k2[i][j]+n*m);
    }
}

}
int dfs(int u){
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(!vis[v]){
vis[v]=1;
if(!match[v]||dfs(match[v])){
match[u]=v;
match[v]=u;
return 1;
}
}
}
return 0;
}
void debug(){
for(int i=1;i<=n;i){
for(int j=1;j<=m;j
){
cout<[HTML_REMOVED]>n>>m;
build();
// debug();
for(int i=1;i<=cnt1;i){
if(!match[i]){
memset(vis,0,sizeof(vis));
if(dfs(i)) sum
;
}
}
cout<<sum<<endl;
}



活动打卡代码 AcWing 376. 机器任务

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;
const int N = 105, M = 2e3 + 5;
struct E{int v, next;} e[M];
int n, m, k, no, u, v, len, h[N], mat[N];
bool vis[N];
void add(int u, int v) {e[len].v = v; e[len].next = h[u]; h[u] = len;}
bool dfs(int u) {
for (int j = h[u]; j; j = e[j].next) {
int v = e[j].v;
if (vis[v]) continue; vis[v] = true;
if (!mat[v] || dfs(mat[v])) {
mat[v] = u; return true;
}
}
return false;
}
int main() {
while (scanf(“%d”, &n), n) {
scanf(“%d%d”, &m, &k);
memset(h, 0, sizeof(h)); len = 0;
memset(mat, 0, sizeof(mat));
for (int i = 1; i <= k; i
) {
scanf(“%d%d%d”, &no, &u, &v);
if (!u || !v) continue;
add(u, v);
}
int ans = 0;
for (int i = 1; i < n; i) {
memset(vis, false, sizeof(vis));
if (dfs(i)) ans
;
}
printf(“%d\n”, ans);
}
return 0;
}