|
C. Draw Grids
结论题，直接找。
题目大意：
两个人玩一个游戏，在已知m,n的前提下一个给(a,b)，一个给(c,d)。满足| a-c | + | b-d | = 1, 1<= a,c<= n, 1 <= b,d <= m。然后把(a,b)和(c,d)连起来。然后满足不能再连相同的边，不能封闭。有一个人不能走的时候就输了。问先手能不能赢
思路：建议多画几种情况，你会发现走法是走过的边数是n*m - 1。然后很明显，走奇数次就赢了，偶数次就输了。
代码：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define ctx cout << "xxxxx" << endl
#define inf 0x3f3f3f3f
#define int long long
#define eps 0.000000001
#define forn for(int i = 1; i <= n; i++)
#define ct1 cout << -1 << endl;
const int INF = 0x3f3f3f3f;
const double pai = acos(-1.0);
bool book[5][5];
signed main(){
int n, m;
cin >> n >> m;
int ans = n*m - 1;
if(ans & 1){
cout << "YES\n";
}else{
cout << "NO\n";
}
}
D. Er Ba Game
if…else题目，题目说什么，你就做什么。
题目大意：
给两组数(a1,b1)和(a2, b2), 比较大小。
相等返回tie。
谁是(2,8)谁就大。
当(a == b)时谁大就大
谁(a==b && x != y)谁就大
当（a!=b && x!=y)就相加模10，谁的模数大谁就大， 模数一样谁的b大谁就大。
思路：直接暴力模拟…
代码：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define ctx cout << "xxxxx" << endl
#define inf 0x3f3f3f3f
#define int long long
#define eps 0.000000001
#define forn for(int i = 1; i <= n; i++)
#define ct1 cout << -1 << endl;
const int INF = 0x3f3f3f3f;
const double pai = acos(-1.0);
string s1 = "first", s2 = "second", s3 = "tie";
void solve() {
int x1, x2, y1, y2;
cin >> x1 >> y1 >> x2 >> y2;
if (x1 > y1)swap(x1, y1);
if (x2 > y2)swap(x2, y2);
if(x1 == x2 && y1 == y2) {
cout << s3 << endl;
return;
}
if (x1 == 2 && y1 == 8) {
if(x2 == 2 && y2 == 8){
cout << s3 << endl;
return;
}
cout << s1 << endl;
return;
}
else if (x2 == 2 && y2 == 8) {
if(x1 == 2 && y1 == 8){
cout << s3 << endl;
return;
}
cout << s2 << endl;
return;
}
if (x1 == y1 && x2 != y2) {
cout << s1 << endl;
return;
}
else if (x2 == y2 && x1 != y1) {
cout << s2 << endl;
return;
}
if (x1 == y1 && x2 == y2) {
if (x1 == x2) {
cout << s3 << endl;
return;
}
else if (x1 < x2) {
cout << s2 << endl;
return;
}
else if (x1 > x2) {
cout << s1 << endl;
return;
}
}
if (x1 != y1 && x2 != y2) {
int tmp1 = (x1 + y1) % 10, tmp2 = (x2 + y2) % 10;
if (tmp1 > tmp2) {
cout << s1 << endl;
return;
}
else if (tmp1 < tmp2) {
cout << s2 << endl;
return;
}
else if (tmp1 == tmp2) {
if (y1 > y2) {
cout << s1 << endl;
return;
}else if(y1 < y2){
cout << s2 << endl;
return;
}
else if(y1 == y2){
cout << s3 << endl;
return;
}
}
}
}
signed main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
F. girlfriends
球体积相交问题，由模板，由公式，据说是高中阿式圆，但是我没学过。
题目大意：
给出四个点A,B,C,D坐标, 然后有两个人R, J。满足|RA| >= k1|RB|, |JC| >= k*|JD|。
求可行动范围的的相交。
思路：
带入两点距离公式，然后化简就会发现这是一个球。然后去网上搜模板。
我只找了最后求值的公式，因为懒的积分和证明…
这里有一个链接可以看一下:
球的相交
代码：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define ctx cout << "xxxxx" << endl
#define inf 0x3f3f3f3f
#define int long long
#define eps 0.000000001
#define forn for(int i = 1; i <= n; i++)
#define ct1 cout << -1 << endl;
const int INF = 0x3f3f3f3f;
const double pai = acos(-1.0);
double getpoint(double a, double b, double k) {
double ans = (a - k * k * b) / (k * k - 1);
if (ans == 0) {
return 0;
}
return -1 * ans;
}
double getr(double a, double b, double k) {
double tmp1 = (a - k * k * b) * (a - k * k * b) - (k * k * b * b - a * a) * (k * k - 1);
double tmp2 = (k * k - 1) * (k * k - 1);
return tmp1 / tmp2;
}
void solve() {
double Ax, Ay, Az;
double Bx, By, Bz;
double Cx, Cy, Cz;
double Dx, Dy, Dz;
cin >> Ax >> Ay >> Az;
cin >> Bx >> By >> Bz;
cin >> Cx >> Cy >> Cz;
cin >> Dx >> Dy >> Dz;
double k1, k2;
cin >> k1 >> k2;
double x1, y1, z1, r1;
x1 = getpoint(Ax, Bx, k1), y1 = getpoint(Ay, By, k1), z1 = getpoint(Az, Bz, k1);
r1 = sqrt(getr(Ax, Bx, k1) + getr(Ay, By, k1) + getr(Az, Bz, k1));
double x2, y2, z2, r2;
x2 = getpoint(Cx, Dx, k2), y2 = getpoint(Cy, Dy, k2), z2 = getpoint(Cz, Dz, k2);
r2 = sqrt(getr(Cx, Dx, k2) + getr(Cy, Dy, k2) + getr(Cz, Dz, k2));
double V1 = (4.00 / 3.00) * pai * r1 * r1 * r1, V2 = (4.00 / 3.00) * pai * r2 * r2 * r2;
double ans = 0;
double d = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) + (z1 - z2) * (z1 - z2));
if (d >= r1 + r2) {
cout << fixed << setprecision(3) << ans << endl;
return;
}
else if (d + r1 < r2) {
cout << fixed << setprecision(3) << V1 << endl;
return;
}
else if (d + r2 <= r1) {
cout << fixed << setprecision(3) << V2 << endl;
return;
}
double h1 = (r1 - (r1 * r1 - r2 * r2 + d * d) / (2.00 * d));
double h2 = (r2 - (r2 * r2 - r1 * r1 + d * d) / (2.00 * d));
V1 = pai * h1 * h1 * (r1 - (1.00 / 3.00) * h1), V2 = pai * h2 * h2 * (r2 - (1.00 / 3.00) * h2);
cout << fixed << setprecision(3) << V1 + V2 << endl;
}
signed main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
代码很多，但思想很简单，如果推了一遍一般都能过。
K. Stack
模拟栈，拓补排序，原谅我还没学…
题目：
有一个数组a, 现在进行栈操作，
Stk is an empty stack
for i = 1 to n :
while ( Stk is not empty ) and ( Stk’s top > a[i] ) :
pop Stk
push a[i]
b[i]=Stk’s size
语言描述太抽象，直接用题目。
现在我们知道一些b的值，请返回满足题意的数组a
思路：
我们把b中的数补全，然后按1，2，… 从右往左依次写入。
这样写是对的，应该是能证明的，但我不会。
代码：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define ctx cout << "xxxxx" << endl
#define inf 0x3f3f3f3f
#define int long long
#define eps 0.000000001
#define forn for(int i = 1; i <= n; i++)
#define ct1 cout << -1 << endl;
const int INF = 0x3f3f3f3f;
const double pai = 3.141592653589;
const int maxn = 1e6 + 10;
struct vv{
int c, d;
};
vv b[maxn];
bool cmp1(vv a, vv b){
if(a.c == b.c) return b.d < a.d;
return a.c < b.c;
}
bool cmp2(vv a, vv b){
return a.d < b.d;
}
signed main(){
int n, k;
cin >> n >> k;
vector<int> ans(n+1);
int tmp = 0;
for(int i = 1; i <= k; i++){
int x, y;
cin >> x >> y;
if(x < y) {
cout << -1 << endl;
return 0;
}
b[x].c = y;
b[x].d = x;
for(int i = tmp+1; i <= x; i++){
int uu = b[tmp].c > b[x].c ? -1 : 1;
if(b[i].c == 0) b[i].c = b[i-1].c;
if(b[i].c != b[x].c) b[i].c += uu;
b[i].d = i;
}
tmp = x;
}
if(tmp < n){
for(int i = tmp+1; i <= n; i++){
b[i].c = b[i-1].c;
b[i].d = i;
}
}
sort(b+1, b+1+n, cmp1);
for(int i = 1; i <= n; i++){
ans[b[i].d] = i;
}
for(int i = 1; i <= n; i++){
cout << ans[i] << " ";
}
}
|