VJ1018

it2023-11-06 86

A - Multiple of 9

#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include <set> typedef long long ll; using namespace std; char ch[1000000]; int main() { ll len, sum; scanf("%s",ch); len = strlen(ch); sum = 0; for(int i = 0; i < len; i++) { sum = sum + ch[i] - '0'; } if(sum % 9 == 0) printf("Yes"); else printf("No"); return 0; }

B 大理石在哪里

题意现有N个大理石，每个大理石上写了一个非负整数。首先把各数从小到大排序，然后回答Q个问题。每个问题问是否有一个大理石写着某个整数x，如果是，还要回答哪个大理石上写着x。排序后的大理石从左到右编号为1～N。（在样例中，为了节约篇幅，所有大理石上的数合并到一行，所有问题也合并到一行。）

样例分析 Sample Input 4 1 2 3 5 1 5 5 2 1 3 3 3 1 2 3 0 0 Sample Output CASE# 1: 5 found at 4 CASE# 2: 2 not found 3 found at 3 输入输出顺序 4 1 //输入4个数，找一个数 2 3 5 1 CASE# 1: 5 //要找的这一个数是5 5 found at 4 //5排在第4 5 2 1 3 3 3 1 CASE# 2: 2 2 not found 3 3 found at 3 0 0

#include <stdio.h> #include <iostream> #include <algorithm> #include <queue> using namespace std; int ar[11000]; int main() { int n, q, a, key=1000000, k = 1; while(scanf("%d%d",&n,&q)!=EOF) { if(n == 0 && q == 0) { break; } for(int i = 1; i <= n; i++) { scanf("%d",&ar[i]); } sort(ar+1,ar+n+1); printf("CASE# %d:\n",k++); while(q--) { scanf("%d",&a); int i = 1; for(i;i<=n;i++) { if(ar[i] == a) { key = i; break; } } if(key == 1000000) printf("%d not found\n",a); else { printf("%d found at %d\n", a, key); key = 1000000; } } } return 0; }

STL如何写袜？

C - Walk on Multiplication Table

直接抄jygg滴题意给你一个整数N，让你从（1，1）点出发，到达（x,y）点，并且（x,y）满足x*y=N,问你(x-1)+(y-1)最小是多少？思路：找N的因子，因为N的大小是2~1e12,所以用sqrt(N)找N的因子完全可以，我们易知，离sqrt（N）越近的两个因子相加的和越小，所以我们只需要找到离sqrt(N)最近的两个N的因子就可以了。 AC代码

D Codeforces-501b

题解：就是给a=b,b=c.让你输出a=c.(中间省略b);可以利用map容器，用其键值和映射分别表示名字的后一个单词和前一个单词；然后查找器键值是否出现过，若出现过将其连接。

AC代码为：

#include<iostream> #include<map> #include<string> using namespace std; int main() { int n; while (cin >> n) { map<string, string> str; while (n--) { string s1, s2; cin >> s1 >> s2; if (!str.count(s1)) str[s2] = s1; else { str[s2] = str[s1]; str.erase(s1); } } cout << str.size() << endl; for (map<string, string>::iterator it = str.begin(); it != str.end(); it++) cout << it->second << " " << it->first << endl; } return 0; }

E-Maximal Value

题意：给你一个B数组，让你找出一个A数组使得：Bi >= max(Ai，Ai+1）

**思路：**一个B可以决定两个A，直接看代码吧，不太好说。

#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include <set> typedef long long ll; using namespace std; int a[1000005]; int b[1000005]; int main() { for (int i=1;i<=1000;i++) b[i]=100005;//将b数组改成最大值 int n; cin >> n; for (int i=1;i<=n-1;i++) { cin >> a[i]; } for (int i=1;i<=n-1;i++) { if(a[i]<b[i]) b[i]=a[i]; if(a[i]<b[i+1]) b[i+1]=a[i]; } ll sum=0; for (int i=1;i<=n;i++) { sum+=b[i] ; } cout << sum << endl; }

F - USACO ORZ HDU - 4277

Sample Input 1 3 2 3 4 Sample Output 1 样例分析第一行输入 1 代表有组测试样例；第二行输入3 代表第一个样例中有3个栅栏；第三行输入3个数代表这3个栅栏的长度；判断用栅栏围成的三角形的个数

暂时不会

G-FUTON

#include <bits/stdc++.h> using namespace std; typedef long long ll; #define re register #define ls (o<<1) #define rs (o<<1|1) //#define m (l+r)/2 #define pb push_back typedef pair<int,int> pii; const double PI= acos(-1.0); const int M = 1e5+7; /* int head[M],cnt=1; void init(int n){cnt=1;for(int i=0;i<=n;i++)head[i]=0;} struct EDGE{int to,nxt,w;}ee[M*2]; void add(int x,int y,int w){ee[++cnt].nxt=head[x],ee[cnt].w=w,ee[cnt].to=y,head[x]=cnt;} */ char s[110][110]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n,m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>(s[i]+1); int ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ if(s[i][j]=='#')continue; if(i>1){ if(s[i-1][j]=='.')ans++; } if(j>1&&s[i][j-1]=='.')ans++; } cout<<ans<<endl; return 0; }

H - Ignatius and the Princess II HDU - 1027

题意：全排列

暂时不会

I 丑数

题意：找出第1500个丑数（1是第一个丑数）分析：所有的丑数都是由丑数*2，*3，*5得到的

#include<cstdio> #include<queue> #include<algorithm> #include<set> using namespace std; int A[1550]; int main() { int a = 1, b = 1, c = 1; int cnt = 1; A[cnt++] = 1; while (cnt < 1501) { int ugly = min(2 * A[a], min(3 * A[b], 5 * A[c])); if (ugly == 2 * A[a]) a++; if (ugly == 3 * A[b]) b++; if (ugly == 5 * A[c]) c++; A[cnt++] = ugly; } printf("The 1500'th ugly number is %d.\n", A[1500]); return 0; } #include <cstdio> #include <iostream> #include <queue> #include <algorithm> #include <set> using namespace std; int ar[1550]; int main() { int a = 1, b = 1, c = 1; int cnt = 1; ar[cnt] = 1; while(cnt < 1501) { int ugly = min( 2 * ar[a],min(3 * ar[b], 5 * ar[c])); if(ugly == 2 * ar[a]) a++; if(ugly == 3 * ar[b]) b++; if(ugly == 5 * ar[c]) c++; cnt++; ar[cnt] = ugly; } printf("The 1500'th ugly number is %d.\n",ar[1500]); return 0; }

J - Andy’s First Dictionary UVA - 10815

题意：给你一段文字，把所有的单词挑出来，然后排序打印、

打印的时候不能打印重复的，因此，在打印的时候一个判断就好。集合set的用法：

1.set是数学上的一个集合，每个元素最多只出现一次，使得省略去重操作。 2.由于string已经定义了“小于”符号，使得存入set中的元素已经从小到大排好序，所以直接用set保存单词集合。 3.steringstream ss，是用来把一些数据定义成一个流，然后向一个东西里面输入。 stringstream ss(s); while(ss>>buf) dict.insert(buf); 4.因为前面已经把s里面的非字母内容全部变成了空格，所以buf会一个单词一个单词的读入，不读空格。 5.set::iterator 的意思是迭代器，是STL中的重要概念，类似于指针的用法。 for(set<string>::iterator it = dict.begin();it != dict.end();++it) cout << *it << endl; #include<iostream> #include<string> #include<sstream> #include<set> using namespace std; int main() { string s; string buf; set<string> p; while (cin>>s) { for (int i = 0;i < s.length();i++) { if (isalpha(s[i]))/*isalpha是一种函数：判断字符ch是否为英文字母，若为英文字母，返回非0（小写字母为2，大写字母为1）。若不是字母，返回0。*/ { s[i] = tolower(s[i]);/*tolower是一种函数，功能是把字母字符转换成小写，非字母字符不做出处理。*/ } else { s[i] = ' '; } } stringstream ss(s);//s流入ss while (ss >> buf)//ss的流出必须用while { p.insert(buf); } } for (set<string>::iterator it = p.begin();it != p.end();it++) cout << *it << endl; }

K - The Blocks Problem UVA - 101

暂时不会

L - Ananagrams UVA - 156

分析 map容器的模板题，判断是否能交换字母顺序变成另外一个单词，只需要先把单词都变成小写字母。然后再按字母字典序排序，放入map中进行计数，然后把计数为一的再放入另一个容器，再排序输出即可

#include <bits/stdc++.h> using namespace std; deque<string> dq1,dq2;/*两个容器，第一个用来把所有的字符串装下，第二个只装符合要求的字符串*/ map<string,int> cnt;//映射：可理解为自变量是字符串，因变量是出现次数 string tran(string a)/*调用一个函数，把每次输入的字符串都转化为小写，且按字典序排序*/ { for(int i=0; i<a.size(); i++) { a[i]=tolower(a[i]); } sort(a.begin(),a.end()); return a; } int main() { string s; while(cin>>s) { if(s[0]=='#') break; string ans=tran(s);//ans存变化后的字符串 dq1.push_back(s);//原来的字符串放在dp1中储存 if(!cnt.count(ans))/*判断映射中是否存在ans，不存在建立一个映射，ans——>0，可理解为初始化*/ cnt[ans]=0; cnt[ans]++;//自增，每次都要执行，用来记录ans出现的次数 } for(int i=0; i<dq1.size(); i++) { if(cnt[tran(dq1[i])]==1)//判断dp1中每个字符串转化后出现的次数 dq2.push_back(dq1[i]);/*出现一次的，既符合条件的，放到qp2中*/ } sort(dq2.begin(),dq2.end());//排序，输出 for(int i=0; i<dq2.size(); i++) { cout<<dq2[i]<<endl; } return 0; }

M - Team Queue UVA - 540

`N - Neq Min

题目翻译给一个长度为 N 的序列，记为 P1, P2, …, PN。要求我们找序列第 i 个数列中，找出最小的非负数，而且这个数没有在 P1, P2, …, Pi 中。

题目分析 AtCoder 的 C 题是一个玄学，有时候会很水，比如这次，考数据结构的知识点。

要找出最小的非零负数，而且这个数必须没有在 P1, P2, …, Pi 列中出现。那就很简单了，自己记录一下出现的数据即可，也就是在出现的数据做标记，然后每个询问，查找第一个没有标记的就是答案了。

但是要注意，本题有 N 个查询，如果每次都是从 0 到 2e5 查询的话，数据量大，会出现 TLE 哦。因为你的复杂度是 O(N^2) 的。

简单优化一下就可以了。也就是记录上次找到的 ans，下一次查询，从上次 ans 位置开始查询即可。

样例数据 2 分析看不明白，我们来分析一下样例数据。样例数据 1 比较小，我们选择样例数据 2。

根据样例 2，我们可以知道 N=10，读入的数据次序为：5 4 3 2 1 0 7 7 6 6。

初始状态我们可以定义一个 11 大小状态数组，注意一定要比 N 大，可以考虑一下为什么？我们用 0 表示没有出现，用 1 表示出现。那么这个数组的初始状态为：

f[0]=0; f[1]=0; f[2]=0; f[3]=0; f[4]=0; f[5]=0; f[6]=0; f[7]=0; f[8]=0; f[9]=0; f[10]=0; f[11]=0;

用 ans 表示上次回答，因此 ans 初始化也为 0。

第一个数据 5 读取数据为 5。这样我们先将 f[5] 设置为 1。这样状态数组变为：

f[0]=0; f[1]=0; f[2]=0; f[3]=0; f[4]=0; f[5]=1; f[6]=0; f[7]=0; f[8]=0; f[9]=0; f[10]=0; f[11]=0;