标签：CCFCSP 2309 真题 int double pos cin id mod

-1.坐标变换（Ⅰ

分析

签到题√

AC：不够精简

#include<iostream>
#include<vector>
using namespace std;
const int maxn=100;
int dxy[2];
int xy[maxn+1][2];

int main(){
    int m,n;
    cin>>n>>m;
    int dx=0,dy=0;
    while(n--){//操作
        cin>>dx>>dy;
        dxy[0]+=dx;
        dxy[1]+=dy;
    }
    int num;
    for(int i=0;m--;i++){
        for(int j=0;j<2;j++){
            cin>>num;
            xy[i][j]=num;
        }
        xy[i][0]+=dxy[0];
        xy[i][1]+=dxy[1];
        cout<<xy[i][0]<<' '<<xy[i][1]<<endl;
    }
    return 0;
}

AC：省流版

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, m; cin >> n >> m;
    long long dx = 0, dy = 0;
    long long x, y;

    while(n --) {
        cin >> x >> y;
        dx += x; dy += y;
    }
    while(m --){
        cin >> x >> y;
        cout << x + dx <<" " << y + dy << endl;
    }
    return 0;
}

-2.坐标变换（Ⅱ

分析

测试数据

10 5
2 0.59
2 4.956
1 0.997
1 1.364
1 1.242
1 0.82
2 2.824
1 0.716
2 0.178
2 4.094
1 6 -953188 -946637
1 9 969538 848081
4 7 -114758 522223
1 9 -535079 601597
8 8 159430 -511187

UNAC：精度&超时

每计算一次，都会损失一点精度
所以要先处理完数据，在计算
另外：在双循环的if判断结构中
- else的左值需要注意不要都为x，y
- 存在先写后读冲突
thete是弧度制，cmath三角函数也是弧度制
不需要引用pi

#include<iostream>
#include<cmath>
using namespace std;
const int maxn=1000;//100000
double oppo[maxn+1][2+1];
double a[maxn+1][4+1];

int main(){
    double n,m;
    cin>>n>>m;
    int row=1;
    double n1,n2;
    while(n--){//操作
        cin>>n1>>n2;
        oppo[row][1]=n1;
        oppo[row][2]=n2;
        row++;
    }
    double num;
    for(int f1=1;m--;f1++){//坐标
        for(int f2=1;f2<5;f2++){
            cin>>num;
            a[f1][f2]=num;
        }
        double x=a[f1][3];
        double y=a[f1][4];
        for(int i=a[f1][1];i<=a[f1][2];i++){
            if(oppo[i][1]==1){
                double k=oppo[i][2];
                x*=k;
                y*=k;
            }
            else{
                double theta=oppo[i][2];
                a[f1][3]=x*cos(theta)-y*sin(theta);
                a[f1][4]=x*sin(theta)+y*cos(theta);
            }
        }
        cout<<x<<' '<<y<<endl;
    }
    return 0;
}

UNAC2：超时

将原数转为弧度制
op操作完之后再还原

#include<iostream>
#include<cmath>
#define PI 3.1415926
using namespace std;
const int maxn=1000;//100000
double oppo[maxn+1][2+1];
double a[maxn+1][4+1];

int main(){
    double n,m;
    cin>>n>>m;
    int row=1;
    double n1,n2;
    while(n--){//存储操作
        cin>>n1>>n2;
        oppo[row][1]=n1;
        oppo[row][2]=n2;
        row++;
    }
    double num;
    for(int f1=1;m--;f1++){//影响坐标
        for(int f2=1;f2<5;f2++){
            cin>>num;
            a[f1][f2]=num;
        }
        double x=a[f1][3],y=a[f1][4];
        double R=sqrt(x*x+y*y);
        double theta=atan(y/x);//arctan
        for(int i=a[f1][1];i<=a[f1][2];i++){
            if(oppo[i][1]==1){
                double k=oppo[i][2];
                R*=k;
            }
            if(oppo[i][1]==2){
                double t=oppo[i][2];
                theta+=t;
            }
        }
/*testing:
1 1
2 0.523
1 1 1 1.732
*/
        printf("%.3f",R*cos(theta));
        cout<<' ';
        printf("%.3f",R*sin(theta));
        cout<<endl;
    }
    return 0;
}

AC：

一维数组
- 往后累加
- 取值找平均（两端之和除以二

#include<bits/stdc++.h>
using namespace std;
const int N = 100005;

double k[N] = {1};//strench
double s[N] = {0};//rotate

int main()
{
    int n,m; cin>>n>>m;
    k[0] = 1;
    s[0] = 0;

    for(int i = 1;i <= n;i ++){
        int type; cin>>type;
        double w; cin>>w;
        if(type == 1){
            k[i] = k[i - 1] * w;
            s[i] = s[i - 1];
        }
        else{
            s[i] = s[i - 1] + w;
            k[i] = k[i - 1];
        }
    }

    for(int l = 0;l < m;l ++){
        int left,right;
        double x,y;
        cin>>left>>right>>x>>y;
        double ki = k[right] / k[left - 1];
        x *= ki;
        y *= ki;

        double sita = s[right] - s[left - 1];
        double xi = x,yi = y;
        x = xi * cos(sita) - yi * sin(sita);
        y = xi * sin(sita) + yi * cos(sita);

        printf("%5f",x);
        cout<<" ";
        printf("%5f",y);
        cout<<endl;
    }
    return 0;
}

-3.梯度求解

分析

求偏导
逆波兰--栈

比起传统的思路，先去处理表达式，然后再对输入的变量求导，然后再带入值计算，本题的做法更为直接，直接和答案对标。

在这段代码中，先拿到需要求导的自变量，再对函数做处理。看似好像会对表达式做重复处理，但是单次处理会变得简单很多；

AC：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005;
const int mod = 1e9 + 7;

ll coef[N];
int n, m, to_solve;
vector<string> vec;

void solve() {
    //用map<ll, ll>来保存一个多项式,第一个key字段为指数,value字段为系数
    stack<map<ll, ll>> expr;
    for (auto& str: vec) {
        if (str.empty()) {continue;}
        if (str[0] == 'x') {  // var
            // 使用标准库函数提取序号
            ll index = atoi(str.substr(1).c_str());

            map<ll, ll> tp;
            if (index == to_solve) {
                tp[1] = 1;   //为目标变量则指数为1
            } 

            else {
                tp[0] = coef[index] % mod;   //否则视为常量
            }
            expr.push(tp);
        } 

        else if (str.size() == 1 && !isdigit(str[0])) { // operator
            auto pre = expr.top(); expr.pop();
            auto suf = expr.top(); expr.pop();
            map<ll, ll> res;

            if (str == "+") {
                for(auto& p: pre) {
                    res[p.first] = (p.second % mod);
                }
                for (auto& p: suf) {
                    res[p.first] = (res[p.first] + p.second) % mod;
                }
            } 
            else if (str == "-") {
                for(auto& p: suf) {
                    res[p.first] = (p.second % mod);
                }
                for (auto& p: pre) {
                    res[p.first] = (res[p.first] - p.second) % mod;
                }
            } 
            else {
                for (auto& p: pre) {
                    for (auto& q: suf) {
                        //指数相加，系数相乘
                        ll zs = p.first + q.first;
                        ll bs = (p.second * q.second) % mod;
                        res[zs] = (res[zs] + bs) % mod;
                    }
                }
            }

            expr.push(res);
        } 

        else { // digit常数项
            ll digit = atoi(str.c_str());
            digit %= mod;
            map<ll, ll> tp;
            tp[0] = digit;
            expr.push(tp);
        }
    }

    assert(expr.size() == 1);   //最终只有一个表达式才是合法的

    ll res = 0;

    while (!expr.empty()) {
        auto final_expr = expr.top();
        expr.pop();

        for (auto& p: final_expr) {  
            // 遍历表达式里面的每一个pair对
            ll pw = 1;

            //指数×系数, 也就是把指数放下来,系数减一, 遵循求导法则
            ll bs = (p.second * p.first) % mod;
            ll c = p.first - 1;
            while (c > 0) {
                c--;
                pw = (pw * coef[to_solve]) % mod;
            }

            pw = (pw * bs) % mod;  //x的c次方×系数得到当前项的和

            res = (res + pw) % mod;
        }
    }

    res %= mod;
    res = (res + mod) % mod;   //针对题干的第二个提示

    cout << res << '\n';


}
int main() {
    cin >> n >> m;
    getchar();   //根据输入做的一个调整

    string line, tmp;
    getline(cin, line);
    stringstream sin(line);
    while (sin >> tmp) {
        vec.push_back(tmp);
    }
    while (m --) {
        cin >> to_solve;
        for (int i = 1; i <= n; i++) {
            cin >> coef[i];
        }
        solve();
    }
}

~~什么勾八~~

-4.阴阳龙

分析：

AC：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
 
const int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, p, q;
    cin >> n >> m >> p >> q;
    vector<array<int, 2>> pos(p);
    unordered_map<int, set<array<int, 2>>> row, col, ld, rd;
    auto insert = [&](int id){
        int x = pos[id][0], y = pos[id][1];
        row[x].insert({y, id});
        col[y].insert({x, id});
        ld[x + y].insert({y, id});
        rd[x - y].insert({y, id});
    };
    auto remove = [&](int id){
        int x = pos[id][0], y = pos[id][1];
        row[x].erase({y, id});
        col[y].erase({x, id});
        ld[x + y].erase({y, id});
        rd[x - y].erase({y, id});
    };
    for(int i = 0; i < p; ++ i){
        cin >> pos[i][0] >> pos[i][1];
        insert(i);
    }
    for(int i = 0; i < q; ++ i){
        int u, v, t;
        cin >> u >> v >> t;
        vector<array<int, 3>> candidate;
 
        auto search = [&](const set<array<int, 2>>& people, int d, int dirr, int dirl){
            auto pos = people.lower_bound(array<int, 2>{d, p});
            if (pos != people.end()){
                candidate.push_back({(*pos)[0] - d, (*pos)[1], dirr});
            }
            if (pos != people.begin()){
                pos = prev(pos);
                if ((*pos)[0] == d && pos != people.begin())
                    pos = prev(pos);
 
                if ((*pos)[0] != d){
                    candidate.push_back({d - (*pos)[0], (*pos)[1], dirl});
                }
            }
        };
 
        search(row[u], v, 2, 6);
        search(col[v], u, 0, 4);
        search(ld[u + v], v, 3, 7);
        search(rd[u - v], v, 1, 5);
 
        if (candidate.empty())
            continue;
        sort(candidate.begin(), candidate.end(), [&](const array<int, 3>& a, const array<int, 3>& b){
            return a[0] < b[0];
        });
        int mindis = min({u - 1, n - u, v - 1, m - v});
        if (candidate[0][0] > mindis)
            continue;
        mindis = candidate[0][0];
        for(int i = 0; i < candidate.size(); ++ i){
            if (candidate[i][0] != mindis)
                break;
            int dis = candidate[i][0];
            int id = candidate[i][1];
            remove(id);
            int dir = (candidate[i][2] + t) % 8;
            pos[id][0] = u + dis * dx[dir];
            pos[id][1] = v + dis * dy[dir];
            insert(id);
        }
    }
    LL ans = 0;
    for(int i = 0; i < p; ++ i){
        ans ^= (1ll * (i + 1) * pos[i][0] + pos[i][1]);
    }
    cout << ans << '\n';
    return 0;
}

-5.阻击

分析

AC：

标签：CCFCSP,2309,真题,int,double,pos,cin,id,mod
From： https://www.cnblogs.com/Weenz-y/p/17861231.html

【CCFCSP】2309真题笔记