头像

风云学子

复旦大学


访客:1722

离线:3天前


活动打卡代码 AcWing 791. 高精度加法

#include <iostream>
#include <vector>
using namespace std;
vector<int> add(vector<int> &A, vector<int> &B){
    int t = 0;
    vector<int> C;
    for(int i = 0; i < A.size() || i < B.size(); i ++)
    {
        if(i < A.size())    t += A[i];
        if(i < B.size())    t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if(t)  C.push_back(1);
    return C;
}

int main(){
    string a, b;
    cin >> a >> b;
    vector<int> A, B;
    for(int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i >= 0; i --) B.push_back(b[i] - '0');
    auto C = add(A, B);
    for(int i = C.size() - 1; i >= 0; i --)
        printf("%d", C[i]);
    return 0;
}


活动打卡代码 AcWing 792. 高精度减法

#include <iostream>
#include <vector>
using namespace std;
bool cmp(vector<int> &A, vector<int> &B){
    if(A.size() != B.size())    return A.size() > B.size();
    for(int i = A.size() - 1; i >= 0; i --)
        if(A[i] != B[i])    
            return A[i] > B[i];
    return true;
}
vector<int> sub(vector<int> &A, vector<int> &B){
    int t = 0;
    vector<int> C;
    for(int i = 0; i < A.size() || i < B.size(); i ++)
    {
        t = A[i] - t;
        if(i < B.size())    t -= B[i];
        C.push_back((t+10) % 10);
        if(t < 0) t = 1;
        else t = 0;
    }
    while(C.size() > 1 && C.back() == 0)    C.pop_back();
    return C;
}
int main(){
    string a, b;
    cin >> a >> b;
    vector<int> A, B;
    for(int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i >= 0; i --) B.push_back(b[i] - '0');
    if(cmp(A, B))
    {
        auto C = sub(A, B);
        for(int i = C.size() - 1; i >= 0; i --)
            printf("%d", C[i]);
    }
    else
    {
        auto C = sub(B, A);
        printf("-");
        for(int i = C.size() - 1; i >= 0; i --)
            printf("%d", C[i]);
    }
    return 0;
}


新鲜事 原文

风云学子
1个月前
大学最后一个月,Paper录用啦!
图片


活动打卡代码 AcWing 1237. 螺旋折线

风云学子
1个月前
#include <iostream>
using namespace std;
typedef long long ll;
int x, y, n;
int main(){
    cin >> x >> y;
    n = max(abs(x), abs(y));
    if(abs(x) <= y && y >= 0) //在上方
    {
        //cout << "上方" << endl;
        cout << (ll) (2*n-1)*(2*n)+x+n << endl;
    }
    else if(abs(y) <= x) //在右方
    {
        //cout << "右方" << endl;
        cout << (ll) (2*n)*(2*n)+(n-y) << endl; 
    }
    else if(abs(x) <= abs(y)+1 && abs(x) < n) //在下方
    {
        //cout << "下方" << endl;
        cout << (ll) 2*n*(2*n+1)+n-x << endl;
    }
    else
    {
        //cout << "左方" << endl;
        cout << (ll) (2*n-1)*(2*n-1)+n+y-1 << endl;
    }
    return 0;
}


活动打卡代码 AcWing 466. 回文日期

风云学子
1个月前

有一个简单思路,年份逐年递增,每年只可能对应一个回文日期!
因此不需要枚举每一天!
只需要求一下年份的反转,然后判断日期是否合法、是否位于给的日期区间内即可。
C++解法

#include <iostream>
#include <unordered_map>
using namespace std;
unordered_map<int, int> md;
int s1, s2;
void init(){
    md[1] = 31, md[2] = 29, md[3] = 31, md[4] = 30, md[5] = 31, md[6] = 30;
    md[7] = 31, md[8] = 31, md[9] = 30, md[10] = 31, md[11] = 30, md[12] = 31;
}

string getRes(string a){
    string b = "1234";
    int idx = 0;
    for(int i = 3; i >= 0; i --)
        b[idx ++] = a[i];
    return b;
}

bool checkDate(string str){
    int a = (str[0]-'0')*10+str[1]-'0', b = (str[2]-'0')*10+str[3]-'0';
    return b <= md[a];
}

int main(){
    cin >> s1 >> s2;
    int cnt = 0;
    int y1 = s1 / 10000, y2 = s2 / 10000;
    string tps = getRes(to_string(y1));
    string atps = to_string(y1) + tps;
    init();
    if(checkDate(tps) && atps >= to_string(s1) && atps <= to_string(s2)) cnt ++;
    tps = getRes(to_string(y2));
    atps = to_string(y2) + tps;
    if(checkDate(tps) && atps >= to_string(s1) && atps < to_string(s2)) cnt ++;
    for(int i = y1 + 1; i < y2; i ++){
        if(checkDate(getRes(to_string(i)))) cnt ++;
    }
    cout << cnt << endl;
    return 0;
}

Python解法:

import time
def isValidDate(date):
        try:
            time.strptime(date, "%Y%m%d")
            return True
        except:
            return False

s1 = input()
s2 = input()
y1 = s1[0:4]
y2 = s2[0:4]
ry1 = s1[3::-1]
ry2 = s2[3::-1]
cnt = 0
for i in range(int(y1), int(y2) + 1):
    nd = str(i) + str(i)[3::-1]
    if(isValidDate(nd) and nd >= s1 and nd <= s2):
        cnt += 1
print(cnt)


活动打卡代码 AcWing 1204. 错误票据

风云学子
1个月前
#include <iostream>
#include <sstream>
#include <algorithm>
#define N 10010
using namespace std;
int arr[N];
int main(){
    int all, idx = 0;
    scanf("%d", &all);
    getchar();
    while(all -- ){
        string line;
        getline(cin, line);
        stringstream ssin(line);
        while(ssin >> arr[idx]){idx ++;}
    }
    sort(arr, arr + idx);
    int m,n;
    for(int i = 1; i < idx; i ++){
        if(arr[i] - 2 == arr[i - 1])    m = arr[i] - 1;
        else if(arr[i] == arr[i - 1])   n = arr[i];
    }
    cout << m << " " << n << endl;
    return 0;
}


活动打卡代码 AcWing 1236. 递增三元组

风云学子
1个月前

Java死活过不了,应该是输入量太大
这里查找用了二分,还是有很多坑的

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int N;
int A[100010], B[100010], C[100010];
int getSC(int arr[], int tar){
    int l = 0, r = N;
    while(l < r){
        int mid = l + r >> 1;
        if(arr[mid] < tar){
            l = mid + 1;
        }
        else r = mid;
    }
    if(!l) return arr[l] < tar ? 1 : 0;
    return l;
}

int getBC(int arr[], int tar){
    int l = 0, r = N;
    while(l < r){
        int mid = l + r >> 1;
        if(arr[mid] > tar){
            l = mid + 1;
        }
        else r = mid;
    }
    if(!l) return arr[l] > tar ? 1 : 0;
    return l;
}

bool cmp(int &x, int &y){
    return x > y;
}
int main(){
    scanf("%d", &N);
    for(int i = 0; i < N; i ++) scanf("%d", &A[i]);
    for(int i = 0; i < N; i ++) scanf("%d", &B[i]);
    for(int i = 0; i < N; i ++) scanf("%d", &C[i]);
    sort(A, A + N);
    sort(C, C + N, cmp);
    ll cnt = 0;
    for(int i = 0; i < N; i ++){
        ll a = getSC(A, B[i]), c = getBC(C, B[i]);
        //cout << a << " " << B[i] << " " << c << endl;
        cnt += a * c;
    }
    cout << cnt << endl;
    return 0;
}


活动打卡代码 AcWing 1245. 特别数的和

风云学子
1个月前

没想到太好的方法,就直接转成字符串然后查找一下,应该比直接暴力强点。

#include <iostream>
using namespace std;
bool ok(string s){
    int res = 0;
    if(s.find("2") != string::npos) res ++;
    if(s.find("0") != string::npos) res ++;
    if(s.find("1") != string::npos) res ++;
    if(s.find("9") != string::npos) res ++;
    return res > 0;
}

int main(){
    int n, ans = 0;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++){
        if(ok(to_string(i)))
            ans += i;
    }
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 1210. 连号区间数

风云学子
6个月前
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 10010;
int a[N], b[N], len, ans = 0;
bool check(int i, int j){
    if(i == j)  return true;
    sort(a + i, a + j + 1);
    if(a[j] - a[i] != j - i)    return false;
    return true;
}
int main(){
    scanf("%d", &len);
    for(int i = 1; i <= len; i ++)
        scanf("%d", &a[i]);
    for(int i = 1; i <= len; i ++){
        int minv = 10010, maxv = -10010;
        for(int j = i; j <= len; j ++){
            maxv = max(maxv, a[j]), minv = min(minv, a[j]);
            if(j - i == maxv - minv){
                ans ++;
                //printf("%d %d\n", i, j);
            }  
        }
    }

    printf("%d\n", ans);
    return 0;
}


活动打卡代码 AcWing 796. 子矩阵的和

风云学子
6个月前
 #include <cstdio>
 using namespace std;
 int n, m, q, s[10000010];
 int main(){
    scanf("%d %d %d", &n, &m, &q);
    int tmp = 0, ix = 1;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++){
            scanf("%d", &tmp);
            s[ix] = s[ix - 1] + tmp;
            ix ++;
        }
    while(q --){
        int s1, s2, e1, e2, ans = 0;
        scanf("%d %d %d %d", &s1, &s2, &e1, &e2);
        int sx = (s1 - 1) * m + s2, ex = (e1 - 1) * m + e2, ls = e2 - s2;
        for(int i = s1, k = sx; i <= e1; i ++, k += m){
            ans += s[k + ls] - s[k - 1];
            //printf("%d\n", s[k + ls] - s[k]);
        }
        printf("%d\n", ans);
    }
    return 0;
 }