目录
A. Mathematical Addition
题意:给定两个数字u, v,求满足 x u + y v = x + y u + v \frac{x}{u}+\frac{y}{v}=\frac{x+y}{u+v} ux+vy=u+vx+y的x, y( x ≠ 0 , y ≠ 0 x\neq0,y\neq0 x=0,y=0)
思路:两边同时乘以uv(u+v),化简一下就能得到 x = − u 2 , y = v 2 x=-u^2,y=v^2 x=−u2,y=v2
代码:
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <iterator>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define endl "\n"
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(x) cout<<"**"<<x<<"**"<<endl
#define mem(a, b) memset(a, b, sizeof a)
const double eps = 1e-6;
const double pi = acos(-1.0);
const int mod = 1000000007;
const int N = 1e4 + 10;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
IOS
int T; cin>>T;
while(T--)
{
int a, b; cin>>a>>b;
cout<<(ll)-a*a<<" "<<(ll)b*b<<endl;
}
return 0;
}
B. Coloring Rectangles
题意:给定一个 n ∗ m n*m n∗m的红色矩阵,可以任意划分为大于 1 ∗ 1 1*1 1∗1的小矩阵,然后在每个小矩阵中将一部分格子染为蓝色,使得红蓝相间。求最小蓝色数量。
思路: 1 ∗ 3 1*3 1∗3的两红一蓝是最优的,红蓝比为2:1。所以若能全分为 1 ∗ 3 1*3 1∗3就最优,为 n ∗ m / 3 n*m/3 n∗m/3,否则为 n ∗ m / 3 + 1 n*m/3+1 n∗m/3+1。
代码:
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <iterator>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define endl "\n"
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(x) cout<<"**"<<x<<"**"<<endl
#define mem(a, b) memset(a, b, sizeof a)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define sc second
const double eps = 1e-6;
const double pi = acos(-1.0);
const int mod = 1000000007;
const int N = 1e4 + 10;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
IOS
int T; cin>>T;
while(T--)
{
int n, m; cin>>n>>m;
if(!(n%3) || !(m%3)) cout<<(ll)n*m/3<<endl;
else cout<<(ll)n*m/3+1<<endl;
}
return 0;
}
C. Two Arrays
题意:给定两个数组a, b。可以在a数组中选取一段连续的区间,让这个区间的元素都加1。每个元素只能被选择一次。问a数组经过变换后能否和b数组相同。
思路:排个序,比较两个数组对应位置的元素,当他们的差值全部小于等于1就说明可以相同,注意a[i]不能大于b[i] (因为只能a数组元素加1,不能是b数组元素加1,刚开始我这里就wa了)
代码:
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <iterator>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define endl "\n"
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(x) cout<<"**"<<x<<"**"<<endl
#define mem(a, b) memset(a, b, sizeof a)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define sc second
const double eps = 1e-6;
const double pi = acos(-1.0);
const int mod = 1000000007;
const int N = 1e4 + 10;
int a[111], b[111], aa[111], bb[111];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
IOS
int T; cin>>T;
while(T--)
{
int n; cin>>n;
for(int i = 1; i <= n; i++) cin>>a[i];
for(int i = 1; i <= n; i++) cin>>b[i];
sort(a+1, a+n+1);
sort(b+1, b+n+1);
int flag = 0;
for(int i = 1; i <= n; i++)
{
if(abs(a[i]-b[i]) > 1 || a[i] > b[i])
{
flag = 1;
break;
}
}
cout<<(flag == 0 ? "YES":"NO")<<endl;
}
return 0;
}
D. Guess the Permutation
题意:给出数组的长度n,在数组中选择三个位置i , j , k ,翻转数组[ i , j−1 ] , [ j , k ]的元素。每次可以询问一段区间 [l, r] 里逆序对的个数,在最多40次询问里求出i , j , k。(交互题)
思路:二分
!!!!思路一!!!!
确定 i
逆序对数为0的最长区间就是 [1, i ],可以确定左区间为1,二分找右区间 i,需要
l
o
g
2
1
e
9
log_2^{1e9}
log21e9次(最多30次)
确定 j
先给公式:j = i + (ask(i, n) - ask(i+1, n) + 1)
再证明(举栗子)
假设原数组:1 2 3 4 5 6 7 8
翻转后数组:1 5 4 3 2 7 6 8 ( 所以5的下标为 i, 4的下标为 i+1, 6的下标为 j)
具体看这一段区间:
5 4 3 2 逆序对个数为 6
4 3 2 逆序对个数为 3
可以得到:(ask(i, n) - ask(i+1, n) + 1) = 区间长度
则: j = i + 区间长度
确定k
和确定 j 的道理相同:k = j + ask(j, n) - ask(j+1, n)
(最终一共最多查询34次)
!!!!思路二!!!!
方法和思路一差不多,只是先确定 k, 再确定 j, i 。(i, j, k之间的推导式也要变)这里给出代码,就不再做解释了(补济南站去)。
代码:
思路一
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <iterator>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define endl "\n"
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(x) cout<<"**"<<x<<"**"<<endl
#define mem(a, b) memset(a, b, sizeof a)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define sc second
const double eps = 1e-6;
const double pi = acos(-1.0);
const int mod = 1000000007;
const int N = 1e4 + 10;
ll ask(ll l, ll r)
{
ll ans = 0;
cout<<"? "<<l<<" "<<r<<endl;
cout.flush();
cin>>ans;
return ans;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
IOS
int T; cin>>T;
while(T--)
{
ll n; cin>>n;
ll l = 1, r = n, i, j, k;
while(l < r)
{
int mid = (l+r)>>1;
if(ask(1, mid) > 0) r = mid;
else l = mid+1;
}
i = l-1;
j = i + ask(i, n) - ask(i+1, n) + 1;
k = j + ask(j, n) - ask(j+1, n);
cout<<"! "<<i<<" "<<j<<" "<<k<<endl;
cout.flush();
}
return 0;
}
思路二
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <iterator>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <stack>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define endl "\n"
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(x) cout<<"**"<<x<<"**"<<endl
#define mem(a, b) memset(a, b, sizeof a)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define sc second
const double eps = 1e-6;
const double pi = acos(-1.0);
const int mod = 1000000007;
const int N = 1e4 + 10;
ll ask(ll l, ll r)
{
ll ans = 0;
cout<<"? "<<l<<" "<<r<<endl;
cout.flush();
cin>>ans;
return ans;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
IOS
int T; cin>>T;
while(T--)
{
ll n; cin>>n;
ll l = 1, r = n, i, j, k;
ll cnt = ask(1, n);
while(l < r)
{
int mid = (l+r)>>1;
if(ask(1, mid) == cnt) r = mid;
else l = mid+1;
}
if(ask(1, l-1) == cnt) k = l-1;
else k = r;
j = k - cnt + ask(1, k-1);
i = j - (ll)sqrt(ask(1, j-1)*2) - 1;
cout<<"! "<<i<<" "<<j<<" "<<k<<endl;
cout.flush();
}
return 0;
}