头像

nnuJacob

nnu




离线:9天前


活动打卡代码 AcWing 1296. 聪明的燕姿

nnuJacob
19天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = (1 << 20)+ 10;
int primes[N]; // primes[i]:第i个素数 
int minP[N];   // minP[i]:i的最小质因子 
bool st[N];
int cnt = 0;
int n;

void get_primes(int n){ // O(n)

    for(int i = 2; i <= n; i++) {
        if(!st[i]) // 没被筛掉,说明i是个素数 
            primes[cnt++] = i, minP[i] = i; 
        for(int j = 0; primes[j]*i < n; j++) {
            st[primes[j]*i] = true;        // 用primes[j]把primes[j]*i筛掉,且只筛一次,即该合数的最小质因子是primes[j],该条语句只执行一次!
            minP[primes[j]*i] = primes[j]; // primes[j]*i的最小质因子是primes[j]
            if(i % primes[j] == 0)         // primes[j]是i的最小素因数
                break;
        }
    }
}

int sum[N]; // 记录每个素因子出现的次数 
long long product[30];


int main(int argc, char** argv) {
    // 存素数 
    get_primes(N);

    // 存阶乘
    product[1] = 1;
    for(int i = 2; i <= 20; i++){
        product[i] = product[i-1]*i;
    }

    int x;
    while(scanf("%d",&x) != EOF){
//      memset(sum, 0, sizeof(sum)); 导致超时,数组长度10^6, 1^2组就超时
        int tot = 0;
        int pcnt = 0;
        while(x > 1){
            int mp = minP[x];
            sum[pcnt] = 0;
            while(x % mp == 0){
                sum[pcnt]++;
                tot++;
                x /= mp;
            }
            pcnt++;
        }
        long long res = product[tot];
        for(int i = 0; i < pcnt; i++){
            res /= product[sum[i]];
        }
        printf("%d %lld\n",tot, res);
    }
    return 0;
}



活动打卡代码 AcWing 1231. 航班时间

nnuJacob
21天前
#include <iostream>
#include <cstdio>
#include <cstdarg>
#include <algorithm>
#include <cmath>
using namespace std;

int get_delt(){// 飞机起降当地时间差 (s)
    int h1,h2,m1,m2,s1,s2;
    int d=0;
    scanf("%d:%d:%d %d:%d:%d (+%d)", &h1, &m1, &s1, &h2, &m2, &s2, &d);
    return (d*24 + h2 - h1)*3600 + (m2-m1)*60 + s2-s1; 
}

int main(){
    int t;
    cin >> t;
    while(t--){
        int t1 = get_delt(); 
        int t2 = get_delt();

        int delt = min(t1,t2) + fabs(t1 - t2)/2;
        int h = delt/3600;
        int m = (delt/60) % 60;
        int s = delt%60;

        printf("%02d:%02d:%02d\n", h, m, s);
    }
    system("pause");
    return 0;
}


活动打卡代码 AcWing 1241. 外卖店优先级

nnuJacob
21天前
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 100005;

struct She{
    int time,id;
    bool operator <(const She &other){
        if(id != other.id) return id < other.id;
        return time < other.time;
    }
}s[N];

int n,m,t;
int res;

int main(){
    cin >> n >> m >> t;
    for(int i = 0 ; i < m; i++) scanf("%d %d", &s[i].time, &s[i].id);
    // 1. 按照编号、时间排序
    sort(s,s+m);
    int cur_id = s[0].id; // 当前处理的id
    int level = 2;
    bool pri = false;
    for(int i = 1; i < m; i++){
        if(cur_id != s[i].id){ // id改变
            // 查看上个id,T时刻是否优先
            level = level - (t-s[i-1].time);
            if(level <= 3) pri = false;
            if(pri) res++;
            cur_id = s[i].id, level = 2, pri = false; // 更新id    
        }
        else{ // 同一个id
            int delt = s[i].time - s[i-1].time;
            if(delt > 1){ // 优先级可能降低
                level = level - (delt-1); // 降低优先级
                if(level < 0) level = 0;  // 最低为0
                if(level <= 3) pri = false;
                level += 2;               // 优先级增2
                if(level > 5) pri = true;
            }
            else{ // 优先级增加
                level += 2;
                if(level > 5) pri = true;
            }
        }
    }
    // 单独查看最后一个外卖店T时刻是否优先,因为没有下一个订单了
    level = level - (t-s[m-1].time);
    if(level <= 3) pri = false;
    if(pri) res++;
    cout << res;
    system("pause");
    return 0;
}




活动打卡代码 AcWing 1229. 日期问题

nnuJacob
23天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;


int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int a, b, c;
int cnt = 0;
int year, month, day;

struct Date{
    int y, m, d;
    bool operator < (Date &t){
        if(y != t.y) return y < t.y;
        if(m != t.m) return m < t.m;
        if(d != t.d) return d < t.d;
    }
}date[3];

bool is_leap(int  x){
    return x%4 == 0 && x%100 != 0 || x%400 == 0;
}
int get_year(int y){
    if(y > 59) return 1900+y;
    else return 2000+y;
}
int get_month(int m){
    if(m < 1 || m > 12) return 0;
    return m;
}
int get_day(int y, int m, int x){
    if(m != 2) {
        if(x < 1 || x > days[m])
            return 0;
        else 
            return x;
    }
    else{ // m == 2
        if(x < 1 || x > 28+is_leap(y))
            return 0;
        else
            return x;
    }
}

bool exist(int y, int m, int d){
    if(!cnt) return false;
    for(int i = 0 ; i < cnt; i++){
        if(date[i].d == d && date[i].m == m && date[i].y == y)
            return true;
    }
    return false;
}

int main(){
    string str;
    cin >> str;
    a = (str.at(0)-'0') * 10 + str.at(1)-'0';
    b = (str.at(3)-'0') * 10 + str.at(4)-'0';
    c = (str.at(6)-'0') * 10 + str.at(7)-'0';
    // cout << a << " " << b << " " << c << endl;
    year = get_year(a);
    month = get_month(b);
    day= get_day(a,b,c);
    if(year && month && day && !exist(year, month, day)) {
        date[cnt++] = {year, month, day};
    }
    year = get_year(c);
    month = get_month(a);
    day = get_day(c,a,b);
    if(year && month && day && !exist(year, month, day)) {
        date[cnt++] = {year, month, day};
    }
    year = get_year(c);
    month = get_month(b);
    day = get_day(c,b,a);
    if(year && month && day && !exist(year, month, day)) {
        date[cnt++] = {year, month, day};
    }
    sort(date, date+cnt);
    // cout <<  cnt << endl;
    for(int i = 0 ; i < cnt; i++){
        cout << date[i].y << "-";
        if(date[i].m < 10 ) cout << "0";
        cout << date[i].m << "-";
        if(date[i].d < 10 ) cout << "0";
        cout << date[i].d << endl;
    }

    system("pause");
    return 0;
}


活动打卡代码 AcWing 1219. 移动距离

nnuJacob
24天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int w, m, n;

int get_row(int x){
    return x/w;
} 
int get_col(int x){
    int row = get_row(x);

    if(row % 2 == 0) // 正序 
        if(row * w == x) return 0; 
        else return x - row*w;
    else // 倒序列
        if(row * w == x) return w-1; 
        else return w + 1 - (x - row*w);
}


int main(){

    cin >> w >> m >> n;
    int rowm = get_row(m);
    int colm = get_col(m);
    int rown = get_row(n);
    int coln = get_col(n);
    // cout << rowm << " " << colm << endl;
    // cout << rown << " " << coln << endl;
    cout << fabs(rowm - rown) + fabs(coln- colm);
    return 0;
}



活动打卡代码 AcWing 1246. 等差数列

nnuJacob
28天前
#include <iostream>
#include <cstdio>
#include <cstring> 
#include <algorithm>
using namespace std;

#define INF 0xfffffff

const int N = 100005;
int a[N];
int delt[N];
int n;

int gcd(int a, int b){
    return b==0 ? a : gcd(b,a%b);
}

int main(int argc, char** argv) {
    cin >> n;   
    for(int i = 0; i < n; i++) {
        scanf("%d",a+i);
    }
    sort(a,a+n);
    int g = a[1] - a[0];
    for(int i = 1; i < n; i++){
        g = gcd(g, a[i] - a[i-1]);
    }
    if(a[n-1] - a[0])
        cout << (a[n-1] - a[0])/g + 1;
    else
        cout << n;
    return 0;
}


活动打卡代码 AcWing 788. 逆序对的数量

nnuJacob
28天前
#include <iostream>
#include <cstdio>
using namespace std;

const int N = 100005;
int a[N];
int tmp[N];
int n;
long long ans;

void merge_sort(int left, int right){
    // 1. 边界 
    if(left >= right) return;

    // 2. 划分子问题
    int mid  = left+right >> 1;
    merge_sort(left, mid);
    merge_sort(mid+1, right);

    // 3. 合并子问题

    // 3.1
    int i = left;
    int j = mid+1;
    int k = 0;
    while(i <= mid && j <= right)
        if(a[i] <= a[j])  tmp[k++] = a[i++];
        else tmp[k++] = a[j++], ans += mid-i+1;
    while(i <= mid) tmp[k++] = a[i++]; // 若执行,则j=right+1 
    while(j <= right) tmp[k++] = a[j++];

    // 3.2
    for(i = left, j = 0; i <= right; i++, j++) a[i] = tmp[j];

    // 

}
int main(int argc, char** argv) {
    cin >> n;
    for(int i = 0; i < n; i++) scanf("%d", a+i);
    merge_sort(0, n-1);
    cout << ans;
    return 0;
}


活动打卡代码 AcWing 787. 归并排序

nnuJacob
28天前
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 100005;
int n;
int a[N], tmp[N];

void merge_sort(int left, int right){

    // 1. 边界 
    if(left >= right) return ;

    // 2. 分治子问题:a分为左右 
    int mid = left+right >> 1;
    merge_sort(left, mid);
    merge_sort(mid+1, right);

    // 3. 子问题合并 
    // 3.1 按序copy到tmp数组
    int i = left;  // 左指针 
    int j = mid+1; // 右指针 
    int k = 0;     // tmp数组的指针 
    while(i <= mid && j <= right)
        if(a[i] <= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    while(i <= mid) tmp[k++] = a[i++];
    while(j <= right) tmp[k++] = a[j++];

    // 3.2 tmp数组排好序了,copy回原数组 
    for (i = left, j = 0; i <= right; i++, j++) a[i] = tmp[j];

}

int main(int argc, char** argv) {
    cin >> n;
    for(int i = 0; i < n; i++) scanf("%d",a+i);
    merge_sort(0,n-1);
    for(int i = 0; i < n; i++) printf("%d ",a[i]);
    return 0;
}


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

nnuJacob
28天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};


bool judge(int x){
    int year = x/10000;
    int month = x%10000;
    month = month / 100;
    int day = x %100;
    if(month == 0 || month > 12) return false;
    if((day == 0 || month != 2 && day > days[month])) return false;
    int r = (year%400 == 0 || (year%4 == 0 && year%100 != 0));
    if(month == 2 && day > days[2] + r) return false;
    return true;
}

int main(int argc, char** argv) {
    int date1, date2;
    cin >> date1 >> date2;
    int res = 0;

    for(int i = date1/10000; i < 10000; i++){
        // 1. 构造回文, 
        int date = i; // 回文日期 
        int tmp = i;
        while(tmp){
            date = date*10 + tmp%10;
            tmp /= 10;
        }
        // 2. 判断是否在date1和date2之间 
        if(date < date1 || date > date2)
            continue;
        // 3. 判断是否是合法日期
        if(judge(date))
            res++;
    }
    cout  << res;
    return 0;
}


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

nnuJacob
28天前
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <sstream>
using namespace std;

const int N = 10005;
int n;
int a[N];


int main(int argc, char** argv) {
    cin >> n;
    int cnt = 0;
    string line;
    getline(cin, line);
    while(n--){
        getline(cin, line);
        stringstream ssin(line);
        while(ssin >> a[cnt]) 
            cnt++;
    }
    sort(a,a+cnt);
    int breaked;
    int repeated; 
    for(int i = 1; i < cnt; i++){
        if(a[i] == a[i-1] + 2)
            breaked = a[i-1]+1;
        if (a[i] == a[i-1])
            repeated = a[i];
    }
    cout << breaked << ' ' << repeated;     
    return 0;
}