七天使的通讯
时间限制: 2 Sec 内存限制: 256 MB提交: 412 解决: 120
[提交][状态][讨论版]
题目描述
n个天使排成一条直线，某些天使之间需要互相联系，他们之间的通讯可以通过黑白两种通道中的一种；所有通道必须在直线同侧（另一侧是地面）；为了保证通讯效率，同种颜色的所有通道之间不能相交。请计算能否建立这种通讯方案。
输入
第一行一个数T，表示接下来有T个询问。
对于每个询问：第一行两个数n，m，分别表示有n个天使、需要建立通讯线路的天使有m对；接下来有m行，每行两个数a、b，表示a、b两个天使需要通讯。
输出
对于每个询问，输出一行“sane”表示有可行方案、“non”表示无解
样例输入
1 7 5 1 3 2 7 3 4 7 4 6 5
样例输出
sane
提示
【样例解释】
样例中共有一个询问。
在(1,3)、(4,7)、(5,6)之间连黑色通道，在(2,7)、(3,4)之间连白色通道，每条通道都成功建立，且同种颜色的通道没有相交，所以输出sane。
【数据规模和约定】
对于 20%的数据，1<=n<=50，1<=m<=15
对于
50%的数据，1<=n<=1000，1<=m<=300
对于
100%的数据，1<=n<=5000，1<=m<=1000，1<=T<=10，1<=a<=n，1<=b<=n
数据保证每对(a,b)不重复，且a不等于b
【提示】
当两条线路有一对相同的端点时，这两条线路不相交。
也就是说，对于线路(a,b)和线路(c,d)（a<b且c<d），当且仅当a<c<b<d或者c<a<d<b时这两条线路相交。
我们可以根据它给出来的连边条件来构造一个图，然后染色判断这个图是否有冲突（是否为二分图），若成功了，便可以。
#include<cstdio> #include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<string> using namespace std; int CAS,n,m,color[1007]; int cnt,head[1007],next[2000007],rea[2000007]; struct fzy { int l,r; }a[1007]; bool check(int i,int j) { if (a[i].r<=a[j].l||a[j].r<=a[i].l) return 0; if (a[i].l<=a[j].l&&a[i].r>=a[j].r) return 0; if (a[i].r<=a[j].r&&a[i].l>=a[j].l) return 0; return 1; } void add(int u,int v) { cnt++; next[cnt]=head[u]; head[u]=cnt; rea[cnt]=v; } void dfs(int u) { for (int i=head[u];i!=-1;i=next[i]) { int v=rea[i]; if (color[v]==-1) { color[v]=color[u]^1; dfs(v); } } } int main() { scanf("%d",&CAS); while (CAS--) { cnt=0; memset(head,-1,sizeof(head)); memset(color,-1,sizeof(color)); scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { scanf("%d%d",&a[i].l,&a[i].r); if (a[i].l>a[i].r) swap(a[i].l,a[i].r); for (int j=1;j<i;j++) if (check(i,j)) { add(i,j); add(j,i); } } for (int i=1;i<=m;i++) if (color[i]==-1) { color[i]=0; dfs(i); } int flag=0; for (int i=1;i<=m;i++) { for (int j=head[i];j!=-1;j=next[j]) { int u=i,v=rea[j]; if (color[u]==color[v]) { flag=1; break; } } if (flag==1) break; } if (flag==1) printf("non "); else printf("sane "); } }
问题 B: 都市环游
时间限制: 1 Sec 内存限制: 512 MB提交: 253 解决: 88
[提交][状态][讨论版]
题目描述
因为SJY干的奇怪事情过多，SJY收到了休假的通知，于是他准备在都市间来回旅游。SJY有一辆车子，一开始行驶性能为0，每过1时间行驶性能就会提升1点。每个城市的道路都有性能要求。SJY一共有t时间休息，一开始他位于1号城市（保证1号城市道路要求为0），他希望在n号城市结束旅程。每次穿过一条城市间的路会花费1时间，当然他也可以停留在一个城市不动而花费1时间。当且仅当车子的行驶性能大于等于一个城市，我们才能到达那里。SJY希望知道，旅游的方案模10086后的答案。（只要在某一时刻通过的道路存在一条不相同，就算不同的方案）
输入
第一行三个数n,m,t，表示有n个城市m条道路t时间。
第二行n个数，hi表示第i个城市的道路性能要求。
第三到m+2行，每行两个数u,v，表示城市u与城市v之间有一条单向道路连接（可能有重边）。
输出
包括一个数字，表示旅游的方案模10086。
样例输入
5 17 7 0 2 4 5 3 1 2 2 1 1 3 3 1 1 4 4 1 4 5 5 4 5 3 4 1 2 1 5 3 2 1 2 1 1 2 2 1 1 3
样例输出
245
提示
【数据规模和约定】
对于20%的数据，n<=10,t<=80；
对于50%的数据，n<=30,t<=80；
对于100%的数据，n<=70,m<=1000,t<=100000000,hi<=70。
这道题一看觉得像矩阵乘法，但前几个时间内的矩阵是不断变化的，所以我们能预处理出前max_T的时间内的矩阵。因为（max_T<70)，然后剩下就是一个矩阵乘法啦。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #define rep(i,a,b) for(int i=a;i<=n;i++) using namespace std; #define N 75 int n,m,Time,City_level[N],Highest_time,f[75][75],ans[N][N],c[N][N],b[N][N],map[N][N][N]; void init() { scanf("%d %d %d",&n,&m,&Time); for(int i=1;i<=n;i++) { scanf("%d",&City_level[i]); Highest_time=max(Highest_time,City_level[i]); } for(int tt=1;tt<=min(Time,Highest_time);tt++) for(int i=1;i<=n;i++) { map[tt][i][i]=1; } for(int i=1;i<=m;i++) { int x,y; scanf("%d %d",&x,&y); for(int j=City_level[y];j<=min(Time,Highest_time);j++) { map[j][x][y]++; } } } void DP() { ans[1][1]=1; f[0][1]=1; for(int TT=1;TT<=min(Highest_time,Time);TT++) { memset(c,0,sizeof(c)); rep(i,1,n) rep(j,1,n) rep(k,1,n) { c[i][j]=(c[i][j]+ans[i][k]*map[TT][k][j])%10086; } rep(i,1,n) rep(j,1,n) ans[i][j]=c[i][j]; } } void saowei() { Time-=Highest_time; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) b[i][j]=map[Highest_time][i][j]; while(Time) { if(Time%2==1) { memset(c,0,sizeof(c)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) c[i][j]=(c[i][j]+ans[i][k]*b[k][j])%10086; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) ans[i][j]=c[i][j]; } memset(c,0,sizeof(c)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) { c[i][j]=(c[i][j]+b[i][k]*b[k][j])%10086; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) b[i][j]=c[i][j]; Time/=2; } cout<<ans[1][n]<<endl; } int main() { init(); DP(); saowei(); }
问题 C: 大水题
时间限制: 1 Sec 内存限制: 512 MB提交: 199 解决: 24
[提交][状态][讨论版]
题目描述
dzy 定义一个n^2
位的数的生成矩阵A 为一个大小为n*n
且Aij
为这个数的第i*n+j-n位的矩阵。
现在dzy 有一个数n^2
位的数k，他想知道所有小于等于k
的数的n*n
生成矩阵有多少种。（如果不足n^2 位则补前缀零）
输入
第一行一个数n，第二行一个n^2 位的数k
输出
仅一行表示答案，答案可能很大，你只需输出答案对10^9 + 7 取模后的结果。
样例输入
2 1000
样例输出
954
提示
【数据规模和约定】
对于30% 的数据n<=2
对于100% 的数据n
<=1000，且n为偶数
【提示】
如果两个生成矩阵在其中一个旋转180
度后可以重叠，则称这两个矩阵是相同的。
这道题看题面基本看不懂，但看样列就可以明白，其实让我们求小于k的所有不同种类的数（所谓相同种类就是指相反（在k位）或相同）
所以答案个数就是
令f[i][j][k]表示前i位数，是否紧贴着前i个数，前i个数反转后是否贴紧了后i个数（j=1表示没贴近，j=0表示贴近了；k=1表示没爆炸，k=0表示爆炸了）
所以x=(j||a[i+1]>l),y=(l<a[n-i])||(L==a[n-i]&&k)
f[i+1][x][y]+=f[i][j][k]
还有一个坑，就是strlen写在循环里面每次都会计算，时间复杂度内len^2,TLE;
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define ll long long ll ans,dan; ll n,i,f[1000015][2][2],a[1000015],niyuan=500000004,mod=1000000007; char str[1000005]; int main() { scanf("%lld",&n);n*=n; scanf("%s",str+1); int len=strlen(str+1); for(int i=1;i<=len;i++) a[i]=str[i]-'0',ans=(ans*10+a[i])%mod; f[0][0][1]=1; for(int i=0;i<n;i++) for(int j=0;j<=1;j++) for(int k=0;k<=1;k++) { if(!f[i][j][k]) continue; for(int l=0;l<=9;l++) if(j||a[i+1]>=l) { int x=(j||a[i+1]>l),y=(l<a[n-i]||l==a[n-i]&&k); (f[i+1][x][y]+=f[i][j][k])%=mod; } } dan=(f[n][0][1]+f[n][1][1])%mod; dan=(dan-f[n/2][1][1]-f[n/2][1][0]-f[n/2][0][1])%mod; dan=dan*niyuan%mod; ans=((ans-dan)%mod+mod)%mod; cout<<ans<<endl; }