TOJ 474

題敘

https://toj.tfcis.org/oj/pro/474/
給定一個長方形的長與寬，以及一個整數 $k$

求在長方形中能以連續 $k$ 個格子連線的數量有多少

想法

依序找出橫向、直向、斜向的答案相加即可，數學題

Code

//By Koios1143
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define pii pair<int,int>
using namespace std;
int t;
ll w,h,k;
int main(){
	IOS;
	cin>>t;
	while(t--){
		cin>>w>>h>>k;
		ll A=(w-(k-1)),B=(h-(k-1));
		A=(A>0 ? A : 0),B=(B>0 ? B : 0);
		ll row=h*A;
		ll col=w*B;
		ll diag=2*A*B;
		cout<<row+col+diag<<"\n";
	}
	return 0;
}

複雜度

每次的運算量都不大，總複雜度約為 $O(T)$