1001 Expression
式子不好推啊。见官方题解。
式子知道就方便了。处理好组合数和阶乘。
按区间长度从小到大递推完就好。
# include <iostream>
# include <cstdio>
# include <cstring>
using namespace std;
# define maxn
typedef long long LL;
const LL mod=1e9+;
LL fac[maxn]={},C[maxn][maxn];
LL a[maxn],dp[maxn][maxn];
char op[maxn]; int main(void)
{
for(int i=;i<maxn;i++) fac[i]=(fac[i-]*(LL)i)%mod;
for(int i=;i<maxn;i++) C[i][]=(LL);
for(int i=;i<maxn;i++)
for(int j=;j<=i;j++)
C[i][j]=(C[i-][j]+C[i-][j-])%mod;
int n;
while(~scanf("%d",&n))
{
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++) scanf("%I64d",a+i);
scanf("%s",op+);
for(int i=;i<=n;i++) dp[i][i]=a[i];
for(int len=;len<=n;len++)
{
for(int s=;s+len-<=n;s++)
{
for(int m=s;m<s+len-;m++)
{
LL tem;
if(op[m]=='*') tem=dp[s][m]*dp[m+][s+len-];
else if(op[m]=='+') tem=dp[s][m]*fac[s+len-m-]+dp[m+][s+len-]*fac[m-s];
else tem=dp[s][m]*fac[s+len-m-]-dp[m+][s+len-]*fac[m-s];
dp[s][s+len-]+=tem%mod*C[len-][m-s]%mod;
}
dp[s][s+len-]=(dp[s][s+len-]%mod+mod)%mod;
}
}
printf("%I64d\n",dp[][n]);
}
return ;
}
Aguin
1002 Hack it!
1003 GCD Tree
1004 Too Simple
果然还是图样。置换顺序乘反了。
比赛wa到底。拿了数据才知道错在哪。 QAQ。
# include <iostream>
# include <cstdio>
# include <cstring>
using namespace std;
typedef long long LL;
const LL mod=1e9+;
int a[][],vis[];
LL fac[]={}; LL qpow(LL a,int b)
{
LL d=(LL),t=a;
while(b)
{
if(b%) d=(d*t)%mod;
b/=;
t=(t*t)%mod;
}
return d;
} int main(void)
{
for(int i=;i<=;i++) fac[i]=(fac[i-]*LL(i))%mod;
int n,m;
while(~scanf("%d%d",&n,&m))
{
int ok=,cnt=;
for(int i=;i<=m;i++)
{
scanf("%d",&a[i][]);
if(a[i][]==-) cnt++;
else
{
for(int j=;j<=n;j++) scanf("%d",&a[i][j]);
memset(vis,,sizeof(vis));
for(int j=;j<=n;j++) vis[a[i][j]]++;
for(int j=;j<=n;j++) if(vis[j]!=) ok=;
}
}
if(!cnt) for(int i=;i<=n;i++)
{
int pos=i;
for(int j=m;j>;j--) pos=a[j][pos];
if(pos!=i) ok=;
}
if(!ok) puts("");
else
{
LL ans=;
if(cnt) ans=qpow(fac[n],cnt-);
printf("%I64d\n",ans);
}
}
return ;
}
Aguin
1005 Arithmetic Sequence
以每个点为i。处理一下向前向后能延伸的最大距离。
d1≠d2时。答案为sigma(pre[i]*suf[i])。
d1=d2时。pre[i]相当于以i为右端点的区间数。答案为sigma(pre[i])。
# include <iostream>
# include <cstdio>
using namespace std;
typedef long long LL;
const int maxn=;
int a[maxn],pre[maxn],suf[maxn]; int main(void)
{
int n,d1,d2;
while(~scanf("%d%d%d",&n,&d1,&d2))
{
for(int i=;i<=n;i++) scanf("%d",a+i);
pre[]=; suf[n]=;
for(int i=;i<=n;i++)
{
if(a[i]==a[i-]+d1) pre[i]=pre[i-]+;
else pre[i]=;
}
for(int i=n-;i>;i--)
{
if(a[i]==a[i+]-d2) suf[i]=suf[i+]+;
else suf[i]=;
}
LL ans=;
if(d1==d2) for(int i=;i<=n;i++) ans+=(LL)pre[i];
else for(int i=;i<=n;i++) ans+=(LL)pre[i]*(LL)suf[i];
printf("%I64d\n",ans);
}
return ;
}
Aguin
1007 Travelling Salesman Problem
n或者m为奇数时必然能走完。
全偶数时选择行标加列标为奇数的格子中最小的格子不走。其余都能走。
（因为是从偶数格子出发到偶数格子终止的。所以不存在只选一个行标加列标为偶数的格子不走。其他格子都走的情况。）
具体做法是。设选中格子坐标为(i,j)。如果i为奇。可以先走到（i,j-1）。再绕过选中格子。绕到（i,j+2）。就转变为一边为奇数的情况了。
同理i为偶数先走到(i-1,j)。绕到(i+2,j)。按奇数边的走完。
要注意选中格子i==n或者j==m的情况要特判一下。
【代码丑- -】
# include <iostream>
# include <cstdio>
using namespace std;
# define INF
int n,m,map[][]; void Print_char(int len,char c)
{
for(int i=;i<len;i++) putchar(c);
} void ans_print(int x,int y)
{
if((n-x)%==)
{
int len=m-y;
for(int i=x;i<n;i+=)
{
Print_char(len,'R');
putchar('D');
Print_char(len,'L');
putchar('D');
}
Print_char(len,'R');
}
else
{
int len=n-x;
for(int i=y;i<m;i+=)
{
Print_char(len,'D');
putchar('R');
Print_char(len,'U');
putchar('R');
}
Print_char(len,'D');
}
printf("\n");
return;
} int main(void)
{
while(~scanf("%d%d",&n,&m))
{
int sum=;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
scanf("%d",&map[i][j]);
sum+=map[i][j];
}
}
if(n%||m%)
{
printf("%d\n",sum);
ans_print(,);
continue;
}
int Min=INF,x,y;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if((i+j)%==&&map[i][j]<Min)
{Min=map[i][j];x=i;y=j;}
printf("%d\n",sum-Min);
int xx=,yy=;
if(x%==)
{
while(xx<x-)
{
int len=m-yy;
Print_char(len,'R');
putchar('D');
Print_char(len,'L');
putchar('D');
xx+=;
}
while(yy<y)
{
int len=n-xx;
Print_char(len,'D');
putchar('R');
Print_char(len,'U');
putchar('R');
yy+=;
}
if(x<n)
{
Print_char(m-yy,'R');
putchar('D');
for(int i=m;i>yy;i--)
{
if((i-yy)%) printf("DL");
else printf("UL");
}
putchar('D');
ans_print(x+,y);
}
else
{
putchar('R');
ans_print(x-,y+);
}
}
else
{
while(xx<x)
{
int len=m-yy;
Print_char(len,'R');
putchar('D');
Print_char(len,'L');
putchar('D');
xx+=;
}
while(yy<y-)
{
int len=n-xx;
Print_char(len,'D');
putchar('R');
Print_char(len,'U');
putchar('R');
yy+=;
}
if(y<m)
{
Print_char(n-x,'D');
putchar('R');
for(int i=n;i>xx;i--)
{
if((i-xx)%) printf("RU");
else printf("LU");
}
putchar('R');
ans_print(x,y+);
}
else
{
putchar('D');
ans_print(x+,y-);
}
}
}
return ;
}
Aguin
1010 Sometimes Naive