E.Touring cities
一道很有意思的规律题(?),题目的意思是这样的,有一个n*m的网格,你要从头开始走,经过每一个网格后回来,问一共要走几步,但是走是有条件的,只有|x1-x2|+|y1-y2|=1的情况下可以走过去,可以理解成国际象棋里的黑白格,黑的只能走到白的上面,同理白的只能走到黑格上,也可以理解为一笔画。
那么便有两种情况,首先是格子是为偶数的情况,此时格子的白格数量等于黑格数量,则必有一条线可以按照黑白黑白..这样的顺序连起来,一笔就能画完。
答案易得为
n*m
但是奇数情况则不是必然,如(1,1)是黑的话,则黑格会比白格多一个,则在最后的时候会出现两个黑格,但是我们并不能从黑走到黑,所以我们需要先走到一处我们走过的白再走到黑。
这种情况答案为
n*m+1
但是题目中还标记了有传送门,因为我们知道我们最后会多一个黑,所以前面只要有一个传送门可以把我们从一处黑格传送到另一处黑格并且不是原地传送就可以了,在这种情况下走的格子数还为
n*m
代码:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m,k,f=0;
cin>>n>>m>>k;
while(k--)
{
int x1,x2,y1,y2;
cin>>x1>>y1>>x2>>y2;
if((x1%2==y1%2)&&(x2%2==y2%2)&&(x1!=x2||y1!=y2))
f=1;
}
if((n*m)%2==0||f==1)
{
cout<<n*m<<endl;
}
else cout<<m*n+1<<endl;
}
}
G.Counting regions
题意:一道纯纯的数学题,求奇数正边形完全图内部被分成多少块。
知识点:欧拉公式。
思路:Note that no three diagonals share a point when n is odd.
看到这句解释就能确定这题大概率是用欧拉公式解。
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ULL unsigned long long
#define endl '\n'
#define LL long long
#define PII pair<int,int>
const int N = 500010;
const LL mod = 1000000007;
// #define x first
// #define y second
int n;
int p,b;
int fastpow(int a,int x){
int res=a,ans=1;
while(x){
if(x&1) ans=ans*res%mod;
res=res*res%mod;
x >>= 1;
}
return ans;
}
int inv(int a){
return fastpow(a,mod-2);
}
signed main()
{
cin>>n;
// 欧拉公式:图内交点数量-边的数量+分割的区域数量(包括外界一个大区域)=2
// 因为 分割的区域数量 包括外界一个大区域,所以最后答案要减1;
b=n*(n-1)%mod*inv(2); //C(2,n) 图形直线的总数
p=n*(n-1)%mod*(n-2)%mod*(n-3)%mod*inv(24)%mod; //C(4,n) 图内交点的数量
// b=b+2*p; 边的数量 = n+2*交点数
int ans=b+p-n+1;
cout<<ans%mod<<endl;
}