牛客练习赛30 - A、C

A - 回文日期

题目描述

众所周知，小K是nowcoder的暴政苟管理，所以小K很擅长踢树，虽然本题与踢树无关

小K喜欢将日期排列成yyyy-mm-dd的形式（位数不足添零补齐）的形式，虽然这与小K只会做回文字符串这道水题无关，但小K觉得日期组成的回文串也是挺可爱的。作为一个凉心出题人，小K决定给你一个可爱的问题：给你两个日期，求这两个日期的闭区间内有多少个回文的日期（输入可能包含多组数据）

输入描述:

第一行包含一个整数T，表示有T组数据

接下来T行，每行两个“yyyy-mm-dd"形式的日期

输出描述:

输出共T行，每行输出当前数据的回文日期的个数

 

示例1

输入

复制

1
1926-08-16
2333-12-21

输出

复制

36

备注:

对于100%的数据，1 ≤ ? ≤ 10，且日期的形式一定是 YYYY-MM-DD，且输 入日期一定合法，保证答案的年份不会超过4位

思路：

刚开始想的时候居然暴力枚举日期了，然后就过了30%（qwq我真是看见日期题都怕了，省赛阴影嘤）

后来仔细一想，它说的日期是回文，比如1310-01-31那么可以看见年份的前两位和日期应是回文（13,31），年份后两位和月份应是回文（10，01）

这样我们只用枚举年份就好啦~

对于每一年，找到对应的月份和日期，判断它是不是这一年有的日期，然后再判断回文！

（这个题告诉我，写题前先想一想，再纸上画一画，找到规律和可行的方案，不要直接怼，很浪费时间qwq）

代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<set>
#include<queue>
#include<sstream>
using namespace std;
const int N=10006;

int yue[30]={0,31,28,31,30,31,30,31,31,30,31,30,31};
void yes(int y){
    if(((y%4)==0&&(y%100))||(y%400)==0){
        yue[2]=29;
    }
    else yue[2]=30;
}

int main(){
    int t,a,b,c,d,e,f;
    int yy,mm,dd;
    scanf("%d",&t);
    while(t--){
        scanf("%d-%d-%d",&a,&b,&c);
        scanf("%d-%d-%d",&d,&e,&f);
        int ans=0;
        for(int i=a;i<=d;i++){
            mm=(i%10)*10+(i%100-i%10)/10;
            dd=((i/100)%10)*10+(i/100-(i/100)%10)/10;
            yes(i);
            if(mm>=1&&mm<=12&&dd>=1&&dd<=yue[mm])ans++;
        }
        printf("%d\n",ans);
    }
}

C - 小K的疑惑

题目描述

众所周知，小K是一只连NOIP2018初赛都没有过的蒟蒻，所以小K很擅长dfs序+分块树，但是本题与dfs序+分块树无关。

小K现在心态爆炸了，因为小K被一道简单的数据结构题给卡住了，希望请你来解决它，但是小K又不想太麻烦你，于是将题面进行了简化（其实是出题人懒得写题面了233333）：

    Bob有?个点的树，每条边的长度有一个边权，现在定义???(?,?)代表第?个点到第?个点的距离模2之后的结果。问有多少(?,?,?)满足，???(?,?) = ???(?,?) = ???(?,?)。

 

输入描述:

第一行一个整数?代表点的数量。

接下来? − 1行每行三个数?,?,?代表有一条在?,?之间长度为?的边。

输出描述:

一行一个整数代表有多少对(?,?,?)满足条件。

 

示例1

输入

复制

3
1 2 3
1 3 4

输出

复制

9

备注:

对于100%的数据，1 ≤ ? ≤ 10000，0 ≤ ? ≤ 233。

思路：

看见模2的就应该想到，两点之间的距离只能是0,1。我们现在找的（i，j，k），相互之间的距离只能是1或者0

那么现在我们的任务就还找到相互之间距离是0 的一坨点，以及相互之间距离是1 的一坨点。

经过分析不存在相互之间距离是1 的点，因为奇+奇=偶

我们以1为根节点，到1的距离是1的点，这坨点相互之间距离是0（x个点）；到1的距离是0的点，这坨点相互之间距离也是0（y个点）

那么答案就是x^3+y^3

因为可以重复选，我们选3个元素，每个元素都有x种可能，所以x*x*x，y同理（高中数学）

代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<set>
#include<queue>
#include<sstream>
#define ll long long
using namespace std;
const int N=10006;

struct proc{int to,cost,next;};
proc edge[2*N];
int head[N],cnt=0,zero=0,one=0;

void addEdge(int from,int to,int cost){
    edge[cnt].to=to;
    edge[cnt].cost=cost;
    edge[cnt].next=head[from];
    head[from]=cnt++;
}

void dfs(int pre,int now,int cost){
    for(int i=head[now];i!=-1;i=edge[i].next){
        int dot=edge[i].to;
        if(dot==pre)continue;
        if((cost+edge[i].cost)%2==0){zero++;dfs(now,dot,0);}
        else {one++;dfs(now,dot,1);}
    }
    return ;
}

int main(){
    int n,s,e,c;
    memset(head,-1,sizeof(head));
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        scanf("%d%d%d",&s,&e,&c);
        addEdge(s,e,c);
        addEdge(e,s,c);
    }
    zero++;
    dfs(0,1,0);
    ll ans=(ll)one*(ll)one*(ll)one+(ll)zero*(ll)zero*(ll)zero;
    printf("%lld\n",ans);
}