链接：https://witacm.com/problemset.php?p=11
A : 过了几天
写时间或者日期内的题目时先把单位统一化成低级单位，计算完成后再化成标准单位。
输入的t的范围由于编码原因没有显示出来
# include <iostream>
struct date {
int year;
int month;
int day;
};
int mon[20] = {
0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool isLeap(int year) {
return (year % 400 == 0) || (year % 4 == 0 && year % 100 != 0);
}
int cnt(date a) {
int y = a.year;
int m = a.month;
int d = a.day;
int sum = 0;
for (int i = 1; i < y; i++) {
if (isLeap(i)) {
sum += 366;
} else {
sum += 365;
}
}
for (int i = 1; i < m; i++) {
if (i == 2) {
if (isLeap(y)) {
sum += 29;
} else {
sum += 28;
}
} else {
sum += mon[i];
}
}
sum += d - 1;
return sum;
}
void solve() {
date d1, d2;
char c;
std::cin >> d1.year >> c >> d1.month >> c >> d1.day
>> d2.year >> c >> d2.month >> c >> d2.day;
int num1 = cnt(d1);
int num2 = cnt(d2);
std::cout << num2 - num1 + 1 << "\n";
}
int main() {
int T;
std::cin >> T;
while (T--) {
solve();
}
return 0;
}
B. 排列数字
# include <iostream>
# include <algorithm>
bool cmp(int a, int b) {
return a > b;
}
int main() {
int a[10] = {
10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
int n, k;
std::cin >> n >> k;
int cnt = 0;
do {
cnt++;
if (cnt == k) {
break;
}
} while (std::next_permutation(a + 10 - n, a + 10, cmp));
for (int i = 10 - n; i < 10; i++) {
std::cout << a[i] << " ";
}
return 0;
}
# include <iostream>
# include <algorithm>
int main() {
int a[10] = {
10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
int n, k;
std::cin >> n >> k;
int cnt = 0;
do {
cnt++;
if (cnt == k) {
break;
}
} while (std::next_permutation(a + 10 - n, a + 10, std::greater<int>()));
for (int i = 10 - n; i < 10; i++) {
std::cout << a[i] << " ";
}
return 0;
}
# include <iostream>
# include <algorithm>
struct d{
int num;
bool operator < (d rhs) {
return this->num > rhs.num;
}
};
int main() {
d a[10];
for (int i = 0; i < 10; i++) {
a[i].num = 10 - i;
}
int n, k;
std::cin >> n >> k;
int cnt = 0;
do {
cnt++;
if (cnt == k) {
break;
}
} while (std::next_permutation(a + 10 - n, a + 10));
for (int i = 10 - n; i < 10; i++) {
std::cout << a[i].num << " ";
}
return 0;
}
#include <iostream>
#include <algorithm>
int a[15] = {
0, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
int choose[15];
bool vis[15];
int n, k;
int cnt = 0;
void dfs(int step) {
if (cnt > k) {
return;
}
if (step == n + 1) {
cnt++;
if (cnt == k) {
for (int i = 1; i <= n; i++) {
std::cout << choose[i] << " ";
}
return;
}
return;
}
for (int i = n; i >= 1; i--) {
if (!vis[i]) {
vis[i] = true;
choose[step] = a[10 - i + 1];
dfs(step + 1);
vis[i] = false;
}
}
}
int main() {
std::cin >> n >> k;
dfs(1);
return 0;
}
C. Simple in Naive
三关键字排序
1.
# include <iostream>
# include <set>
# include <algorithm>
# include <cstdio>
struct person {
int id;
char c;
int num;
bool operator < (person rhs) {
if (c != rhs.c) {
return c < rhs.c;
} else {
if (num != rhs.num) {
return num > rhs.num;
}
return id < rhs.id;
}
}
};
const int maxn = 1e5 + 5;
person p[maxn];
std::set<int> st;
void solve1() {
int Q;
scanf("%d", &Q);
int t;
while (Q--) {
scanf("%d", &t);
puts("YES");
}
}
int main() {
int n, T;
std::cin >> n >> T;
for (int i = 1; i <= n; i++) {
scanf(" %c%d", &p[i].c, &p[i].num);
p[i].id = i;
}
if (T >= n) {
solve1();
return 0;
}
std::sort(p + 1, p + n + 1);
for (int i = 1; i <= T; i++) {
st.insert(p[i].id);
}
int Q;
std::cin >> Q;
while (Q--) {
int t;
scanf("%d", &t);
if (st.find(t) != st.end()) {
puts("YES");
} else {
puts("NO");
}
}
return 0;
}
# include <iostream>
# include <algorithm>
# include <cstdio>
struct person {
int id;
char c;
int num;
bool operator < (person rhs) {
if (c != rhs.c) {
return c < rhs.c;
} else {
if (num != rhs.num) {
return num > rhs.num;
}
return id < rhs.id;
}
}
};
const int maxn = 1e5 + 5;
person p[maxn];
bool vis[maxn];
void solve1() {
int Q;
scanf("%d", &Q);
int t;
while (Q--) {
scanf("%d", &t);
puts("YES");
}
}
int main() {
int n, T;
std::cin >> n >> T;
for (int i = 1; i <= n; i++) {
scanf(" %c%d", &p[i].c, &p[i].num);
p[i].id = i;
}
if (T >= n) {
solve1();
return 0;
}
std::sort(p + 1, p + n + 1);
for (int i = 1; i <= T; i++) {
vis[p[i].id] = true;
}
int Q;
std::cin >> Q;
while (Q--) {
int t;
scanf("%d", &t);
if (vis[t]) {
puts("YES");
} else {
puts("NO");
}
}
return 0;
}
D. 千禧之数
改编自武汉工程大学计算机科学与工程学院第二届程序设计新生赛（预选赛）的D题
本来想卡一个 O ( n ) O(\sqrt n) O(n)的后来看到AC的人后发现自己大意了没有卡
#include <iostream>
typedef long long ll;
int main()
{
int n;
std::cin >> n;
ll sum = 0;
for (int j = 2; j <= n / j; j++)
{
if (n % j == 0)
{
sum += j;
while (n % j == 0)
{
n /= j;
}
}
}
if (n > 1) {
sum += n;
}
if (sum >= 2000)
{
std::cout << "Yes";
}
else
{
std::cout << "No";
}
return 0;
}
E. 喜新厌旧
改编自 武汉工程大学计算机科学与工程学院第二届程序设计新生赛的J题
样例属于自恋行为请勿模仿
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
std::string t;
std::string s;
int main()
{
std::cin >> t >> s;
std::sort(t.begin(), t.end());
int j = 0;
for (int i = 0; i < s.size(); i++)
{
if (s[i] <= t[j])
{
putchar(s[i]);
continue;
}
else
{
putchar(t[j++]);
}
}
return 0;
}
F. 探亲
改编自武汉工程大学第一届程序设计女生赛的C题
邀请码 2020wfinal
两个bfs
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int,int> PII;
const int N=1010;
int m,n;
queue<PII> q;
char g[N][N];
int d[N][N];
int bfs(int x1,int y1,int x2,int y2){
memset(d,-1,sizeof d);
while (q.size()) {
q.pop();
}
q.push({
x1,y1});
d[x1][y1]=0;
while(q.size()){
PII t=q.front();
q.pop();
if(t.first==x2 && t.second==y2) return d[x2][y2];
int dx[]={
-1,0,1,0};
int dy[]={
0,-1,0,1};
for(int i=0;i<4;i++){
int x=t.first+dx[i];
int y=t.second+dy[i];
if(x>0 && x<=n && y>0 && y<=m && g[x][y]=='.' && d[x][y]==-1){
d[x][y]=d[t.first][t.second]+1;
q.push({
x,y});
}
}
}
return d[x2][y2];
}
int main(){
int T;
cin>>T;
while(T--){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>g[i][j];
int x1,y1,x2,y2,x3,y3;
cin>>x1>>y1>>x2>>y2>>x3>>y3;
int res1=bfs(x1,y1,x2,y2);
int res2=bfs(x2,y2,x3,y3);
//cout<<res1<<" "<<res2<<" ";
if(res1==-1 || res2== -1) cout<<"-1"<<endl;
else cout<<res1+res2<<endl;
}
return 0;
}
G. 计算器
搬运自2019年武汉科技大学菜鸟杯
模拟即可
#include<stdio.h>
#include<string.h>
const int MAXN=1e6+5;
char s[MAXN];
char ss[MAXN];
int a,n;
int main()
{
scanf("%s%d",s+1,&n);
int len=strlen(s+1);
for(int i=1;i<=len;i++)a=a*10+s[i]-'0';
for(int i=1;i<=n;i++)
{
scanf("%s",ss+1);
for(int j=1;j<=9;j++)
{
int flag=1;
for(int k=1;k<=len;k++)
{
int x=s[k]-'0',y=ss[k]-'0';
if(x*j%10!=y)
{
flag=0;
break;
}
}
if(flag)
{
a*=j;
break;
}
}
strcpy(s+1,ss+1);
}
printf("%d",a);
}
H. ZZZ的银河女装传说
搬运自2019年武汉科技大学菜鸟杯
题意可以转化成求最少变换次数让字符串变为左边一串连续的’.‘序列，右边一串连续的’#‘序列，或者全变为’.‘序列或者’#‘序列。
我们可以预处理出’.‘和’#‘的前缀和,a[i]代表前i个字符里有a[i]个’.’, b[i]代表前i个字符里有b[i]个’#’，那么可以直接遍历字符串，枚举每个点为’.‘和’#‘序列的分界点(’.‘的最后一个点)时的情况。要想让衣柜是整齐的，那么只需要把分界点前的’#‘全部变为’.’ (贡献为b[i]),将分界点后的’.‘全部变为’#’ (贡献为a[n]-a[i])。每一次枚举计算答案是O(1)的，所以总复杂度为O(n)。
a n s = m i n ( a n s , b [ i ] + a [ n ] − a [ i ] ) ans=min(ans,b[i]+a[n]-a[i]) ans=min(ans,b[i]+a[n]−a[i])
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register
#define ll long long
#define CL(a,b) memset(a,b,sizeof a)
const int N=2e5+7,inf=0x3f3f3f3f;
char s[N];
int a[N];
int black[N],white[N];
int main()
{
int n;
scanf("%d",&n);
scanf("%s",s);
for(int i=0;i<n;i++)
if(s[i]=='.')
a[i+1]=0;
else a[i+1]=1;
int ans=inf;
for(int i=1;i<=n;i++)
if(a[i]==0)
{
white[i]=white[i-1]+1;
black[i]=black[i-1];
}
else
{
black[i]=black[i-1]+1;
white[i]=white[i-1];
}
for(int i=0;i<=n;i++)
ans=min(black[i]+white[n]-white[i],ans);
cout<<ans<<endl;
return 0;
}
论往届题目的重要性
京公网安备 11010502036488号