(http://acm.zzuli.edu.cn/problem.php?id=2267)

題目描述

小浩今年拿到了國家獎(jiǎng)學(xué)金，本來很高興的事，可小浩卻默默不樂，原來是不愿請(qǐng)大家吃飯，小浩查了一下銀行卡，一看還有8位數(shù)，于是嘴角向上微翹，冷笑一聲，說想讓我請(qǐng)客，先能回答出我的問題來。小浩的問題是給定一個(gè)8位的正整數(shù)，如果能判斷出這8位數(shù)是否能組成一個(gè)日期的年月日（年份范圍0000~9999），就可以請(qǐng)客，同學(xué)們還等什么，加油啦！

輸入

輸入有多行，每行一個(gè)8位的正整數(shù)。

輸出

對(duì)于輸入的每個(gè)整數(shù)，如果能組合成一個(gè)日期，輸出“yes"，否則，輸出”no"，每個(gè)輸出占一行。

樣例輸入

32872313
10000000

樣例輸出

yes
no

思路

其實(shí)就是全排列，枚舉所有情況+判斷。（就是這么暴力！）
惦記我。。。

• STL next_permutation
• DFS搜索

AC代碼

• next_permutation

#include<iostream> #include<string.h> #include<algorithm> #define N 100005 #define ll long long using namespace std; int a[N]; int d[N] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int judge (int year) {if(year % 400 == 0 || (year % 100 && year % 4 == 0))return 1;elsereturn 0; } int main (){ //freopen("in.txt", "r", stdin);int n;while (scanf("%d", &n) != EOF) {for (int i = 0; i < 8; i++) {a[i] = n % 10;n /= 10;}sort(a, a + 8);int flag = 0;do {int mon = a[5] + a[4] * 10;int day = a[7] + a[6] * 10;if (mon > 0 && mon <= 12 && day > 0 && day <= 31) {int year = a[0] * 1000 + a[1] * 100 + a[2] * 10 + a[3];if(judge(year))d[2] = 29;elsed[2] = 28;if (mon >= 1 && mon <= 12 && day >= 1 && day <= d[mon] ){flag = 1;break;} } } while (next_permutation(a, a + 8));if(flag)printf("yes\n");elseprintf("no\n");}return 0; }

• DFS

#include<iostream> #include<string.h> #include<algorithm> #define N 100005 #define ll long long using namespace std; int vis[N], a[N], b[N], flag; int d[N] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int judge (int year) { //判斷閏年 if(year % 400 == 0 || (year % 100 && year % 4 == 0))return 1;elsereturn 0; } void dfs(int now) {if (now == 9) {int day = b[7] + b[6] * 10;int mon = b[5] + b[4] * 10;int year = b[0] * 1000 + b[1] * 100 + b[2] * 10 + b[3];if (judge(year))d[2] = 29;elsed[2] = 28;if (mon > 0 && mon <= 12 && day > 0 && day <= d[mon]) {flag = 1;return ;} }for (int i = 0; i < 8; i++) { if (vis[i] == 0) {b[now] = a[i];vis[i] = 1;dfs(now + 1);if (flag == 1)return ;vis[i] = 0;}} } int main (){ //freopen("in.txt", "r", stdin);int n;while (scanf("%d", &n) != EOF) {for (int i = 0; i < 8; i++) {a[i] = n % 10;n /= 10;}memset(vis, 0, sizeof(vis));flag = 0;dfs(1);if (flag) {printf("yes\n");} else {printf("no\n");}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的2267: scholarship（dfs , STL）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。