sb\(O(n^{2})\)传参
暴力一会儿就码好,结果..
祭奠一下死去的代码
died
#include<cstdio>
#define MAX 1010
#define re register
namespace OMA
{
int n,q;
int r,c,l,s;
struct martix
{
int ar[MAX][MAX];
inline friend martix operator +(martix a,int add)
{
for(re int i=r; i<=r+l-1; i++)
{
for(re int j=c; j<=i-r+c; j++)
{ a.ar[i][j] += add; }
}
return a;
}
inline int ans()
{
int sum = 0;
for(re int i=1; i<=n; i++)
{
for(re int j=1; j<=n; j++)
{ sum ^= ar[i][j]; }
}
return sum;
}
inline void print()
{
for(re int i=1; i<=n; i++)
{
for(re int j=1; j<=n; j++)
{
printf("%d ",ar[i][j]);
}
printf("\n");
}
}
}u;
inline int read()
{
int s=0,w=1; char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); }
while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); }
return s*w;
}
signed main()
{
n = read(),q = read();
for(re int i=1; i<=q; i++)
{ r = read(),c = read(),l = read(),s = read(); u = u+s; }
//u.print();
printf("%d\n",u.ans());
return 0;
}
}
signed main()
{ return OMA::main(); }
好吧,其实是我传参的时候传了个1000*1000的矩阵进去,然后就炸了,我真傻,真的打暴力还整花活,还打挂了,给1pts都算便宜我了。
正解:
差分。
Code
#include<cstdio>
#define MAX 2010
#define re register
#define int long long
namespace OMA
{
int n,q,ans;
int r,c,l,s;
int sum[MAX][MAX][2];
inline int read()
{
int s=0,w=1; char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); }
while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); }
return s*w;
}
signed main()
{
n = read(),q = read();
for(re int i=1; i<=q; i++)
{
r = read(),c = read(),l = read(),s = read();
sum[r][c][0] += s,sum[r+l][c][0] -= s;
sum[r][c+1][1] -= s,sum[r+l][c+l+1][1] += s;
}
for(re int i=1; i<=n; i++)
{
int tmp = 0;
for(re int j=1; j<=n; j++)
{
sum[i][j][0] += sum[i-1][j][0],sum[i][j][1] += sum[i-1][j-1][1];
ans ^= tmp += (sum[i][j][0]+sum[i][j][1]);
}
}
printf("%lld\n",ans);
return 0;
}
}
signed main()
{ return OMA::main(); }
考场一看期望直接跳
明显的状压,但更明显的是,数组开不下,所以考虑map,但是会TLE几个点,所以考虑手写hash表,可是太慢了,所以考虑特判,很明显,对于 \(k=n\) 或 \(k=n-1\) 的点,答案即为白色球的个数。特判一下就好,跑得还飞快
特判前:
优化特判后:
Code
#include<cstdio>
#include<cstring>
#include<iostream>
#define re register
#define seed 1000007
namespace OMA
{
struct Hash_map
{
struct node
{
int next;
int len;
int to;
double v;
}star[seed];
int len,cnt,head[seed];
inline double &operator [](int sta)
{
int key = 1LL*sta*len%seed;
for(re int i=head[key]; i; i=star[i].next)
{
if(star[i].to==sta&&star[i].len==len)
{ return star[i].v; }
}
return star[++cnt] = (node){head[key],len,sta,-1},head[key] = cnt,star[cnt].v;
}
}map;
int n,k;
inline double dfs(int len,int sta)
{
if(len==n-k)
{ return 0; }
map.len = len;
if(map[sta]>-1.0)
{ return map[sta]; }
int temp,tmp[50];
map[temp = sta] = 0;
for(re int i=1; i<=len; i++)
{ tmp[i] = temp&1,temp >>= 1; }
for(re int i=1; i<=len/2; i++)
{
double tmp1 = dfs(len-1,((sta>>(len-i+1))<<(len-i))|(sta&((1<<len-i)-1)))+tmp[len-i+1];
double tmp2 = dfs(len-1,((sta>>i)<<(i-1))|(sta&((1<<i-1)-1)))+tmp[i];
map.len = len,map[sta] += 2.0/len*std::max(tmp1,tmp2);
}
if(len&1)
{
double tmp1 = dfs(len-1,(sta>>(len-((len>>1)+1)+1))<<(len-((len>>1)+1))|(sta&((1<<(len-((len>>1)+1)))-1)))+tmp[len/2+1];
map.len = len,map[sta] += 1.0/len*tmp1;
}
return map[sta];
}
int sta,cnt;
char ch[50];
signed main()
{
scanf("%d%d%s",&n,&k,ch+1);
for(re int i=1; i<=n; i++)
{ sta <<= 1; if(ch[i]=='W'){ cnt++,sta++; } }
if(k&&(k==n||k==n-1))
{ printf("%0.10lf\n",(double)cnt); return 0; }
printf("%0.10lf\n",dfs(n,sta));
return 0;
}
}
signed main()
{ return OMA::main(); }
考试的时候奔着1pts的点,结果加了个判断,0pts,你骗分还特判个什么啊
正解:
是个树形dp
快考试了,先咕了
Code
#include<cstdio>
#define MAX 100010
#define re register
#define INF 114514810
namespace OMA
{
int n;
struct Graph
{
int next;
int to;
int w;
}edge[MAX<<1];
int cnt=1,head[MAX];
struct node
{
int a,b;
friend bool operator <(const node &a,const node &b)
{ return a.a==b.a?a.b<b.b:a.a<b.a; }
}dp[MAX][2];
inline int read()
{
int s=0,w=1; char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); }
while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); }
return s*w;
}
inline void add(int u,int v,int w)
{
edge[++cnt].next = head[u];
edge[cnt].to = v;
edge[cnt].w = w;
head[u] = cnt;
}
inline node calc(node a,node b)
{ return (node){a.a+b.a,a.b+b.b}; }
inline node min(node a,node b)
{ return a<b?a:b; }
inline void dfs(int u,int fa,int w)
{
node a = (node){INF,INF},b = (node){0,0};
for(re int i=head[u]; i; i=edge[i].next)
{
int v = edge[i].to,w = edge[i].w;
if(v!=fa)
{
dfs(v,u,w);
node tmp1 = min(calc(a,dp[v][0]),calc(b,dp[v][1]));
node tmp2 = min(calc(b,dp[v][0]),calc(a,dp[v][1]));
a = tmp1,b = tmp2;
}
}
if(w==1)
{ dp[u][0] = (node){INF,INF}; }
else
{ dp[u][0] = min(b,(node){a.a+1,a.b}); }
if(!w)
{ dp[u][1] = (node){INF,INF}; }
else
{ dp[u][1] = min((node){a.a,a.b+1},(node){b.a+1,b.b+1}); }
}
inline int w(int c,int d)
{ return d==2?d:c!=d; }
signed main()
{
n = read();
for(re int i=1; i<=n-1; i++)
{
int u = read(),v = read(),c = read(),d = read();
add(u,v,w(c,d)),add(v,u,w(c,d));
}
dfs(1,0,2);
printf("%d %d\n",dp[1][0].a>>1,dp[1][0].b);
return 0;
}
}
signed main()
{ return OMA::main(); }
手机扫一扫
移动阅读更方便
你可能感兴趣的文章