J题:

题目链接:https://codeforces.com/contest/1015/problem/E1

题解: 对于每个星星,去枚举它是否能够达到要求,如果达到就ans++, 并记录下来。模拟题

#include<bits/stdc++.h>
using namespace std;
char mp[105][105];
int vis[105][105];
int n,m;
struct node{
    int x,y,s;
};
node cnt[500005];
int ti;
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
bool judge(int x, int y, int k){
    int flag = 0;
    for(int i = 0; i < 4; i++){
        int tx = x + k * dir[i][0];
        int ty = y + k * dir[i][1];
        if(tx < 1 || tx > n || ty < 1 || ty > m || mp[tx][ty] != '*') {flag = 1; continue;}
        vis[tx][ty]++;
    }
    if(flag) return false;
    return true;
}
bool judgenow(int x, int y){
    for(int i = 0; i < 4; i++){
        int tx = x +  dir[i][0];
        int ty = y +  dir[i][1];
        if(tx < 1 || tx > n || ty < 1 || ty > m || mp[tx][ty] != '*') {return false;}
    }
    return true;
}
void cancel(int x, int y, int k){
    for(int i = 0; i < 4; i++){
        int tx = x + k * dir[i][0];
        int ty = y + k * dir[i][1];
        if(tx < 1 || tx > n || ty < 1 || ty > m || mp[tx][ty] != '*') continue;
        vis[tx][ty]--;
    }
}
bool check(){
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(!vis[i][j] && mp[i][j] == '*') {
                //cout<<i<<' '<<j;
                return false;
            }
    return true;
}
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> mp[i][j];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++){
            if(mp[i][j] == '*'){
                if(!judgenow(i, j)) continue;
                int k;
                vis[i][j]++;
                for(k = 1; ; k++){
                    if(judge(i, j, k)) continue;
                    else break;
                }
                cancel(i, j, k);
                k--;
                if(k > 0){
                    cnt[++ti].x = i; cnt[ti].y = j; cnt[ti].s = k;
                }
            }
        }
    //cout<<vis[4][2];
    if(!check()){
        cout<<-1;
        return 0;
    }
     cout<<ti<<endl;
    for(int i = 1; i <= ti; i++){
        cout<<cnt[i].x<<' '<<cnt[i].y<<' '<<cnt[i].s<<endl;
    }
    return 0;
}

D题:
题目链接:https://codeforces.com/contest/613/problem/A

题解:很显然对于最远的,只需要找枚举点看哪个点最远即可。而最近的情况套计算几何的模板,那么只求出所有点到线段的距离求出最小值即可。计算几何抄的lrj的白书

#include <bits/stdc++.h>  
using namespace std;  
const double pi = acos(-1);
struct Point {  
    double x, y;  
    Point(double x = 0, double y = 0) : x(x), y(y) {}  
}a[100005];  

typedef Point Vector;  

Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); }  
Vector operator - (Vector A, Vector B) { return Vector(A.x - B.x, A.y - B.y); }  
Vector operator * (Vector A, double p) { return Vector(A.x*p, A.x*p); }  
Vector operator / (Vector A, double p) { return Vector(A.x/p, A.x/p); }  

bool operator < (const Point& a, const Point b) {  
    return a.x < b.x || (a.x == b.x && a.y < b.y);  
}  

const double eps = 1e-10;  

int dcmp(double x) {  
    if(fabs(x) < eps) return 0; else return x < 0 ? -1 : 1;
    //return x < -eps ? -1 : x > eps;
}  

bool operator == (const Point& a, const Point& b) {  
    return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0;  
}  

//向量a的极角  
double Angle(const Vector& v) {  
    return atan2(v.y, v.x); 
}  

//向量点积  
double Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; }  

//向量长度\share\CodeBlocks\templates\wizard\console\cpp  
double Length(Vector A) { return sqrt(Dot(A, A)); }  

//向量夹角  
double Angle(Vector A, Vector B) { return acos(Dot(A, B) / Length(A) / Length(B)); }  

//向量叉积  
double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; }  
//点到线段的距离  
double DistanceToSegment(Point P, Point A, Point B) {  
    if(A == B) return Length(P-A);  
    Vector v1 = B-A, v2 = P-A, v3 = P-B;  
    if(dcmp(Dot(v1, v2)) < 0) return Length(v2);  
    else if(dcmp(Dot(v1, v3)) > 0) return Length(v3);  
    else return fabs(Cross(v1, v2)) / Length(v1);  
}
int main(){
    int n;
    cin >> n;
    Point p;
    cin >> p.x >> p.y;
    double maxx = 0, minn = 0x3f3f3f3f;
    for(int i = 0; i < n; i++) scanf("%lf %lf", &a[i].x, &a[i].y);
    for(int i = 0; i < n; i++){
        maxx = max(maxx, Length(p - a[i]));
        minn = min(minn, DistanceToSegment(p, a[i], a[(i + 1) % n]));
    }
    printf("%.18lf", maxx * maxx * pi - minn * minn * pi);
    return 0;
}

G题:https://codeforces.com/contest/896/problem/A

题解:设f[n]f[n] 为第n个的长度,很显然可以看出 当n>63n > 63 之后长度很显然超过k了。所以可以用从nn递归到00来判断第kk个数字是多少。首先先预处理出题目给的字符串,然后每次查询判断当前是在哪一段即可。

#include <bits/stdc++.h>
#define pa pair<int, int>
#define mp make_pair
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 5;
string s0="What are you doing at the end of the world? Are you busy? Will you save us?";
string s1="What are you doing while sending \"";
string s2="\"? Are you busy? Will you send \"";
string s3="\"?";
ll f[N];
ll len1,len2,len3;
void init() {
    f[0] = s0.length();
    len1 = s1.length();
    len2 = s2.length();
    len3 = s3.length();
    for(int i = 1; i <= 1e5; i++) {
        if(f[i - 1] >= INF) {
            f[i] = INF; continue;
        }
        else f[i] = len1 + f[i - 1] + len2 + f[i - 1] + len3;
    }
}
void dfs(ll n, ll k) {
    if(k > f[n]) {
        cout << "."; return;
    }
    if(n == 0) {
        cout << s0[k - 1]; return;
    }
    if(k <= len1) {
        cout << s1[k - 1]; return;
    }
    else if(k <= len1 + f[n - 1]) {
        dfs(n - 1, k - len1);
    }
    else if(k <= len1 + f[n - 1] + len2) {
        cout << s2[k - len1 - f[n - 1] - 1]; return;
    } 
    else if(k <= len1 + f[n - 1] + len2 + f[n - 1]) {
        dfs(n - 1, k - len1 - f[n - 1] - len2);
    }
    else {
        cout << s3[k - len1 - f[n - 1] - len2 - f[n - 1] - 1]; return;
    }
}
int main() {
    ll q;
    cin >> q;
    init();
    while(q--) {
        ll n,k;
        cin >> n >> k;
        dfs(n, k);
    }
    return 0;
}