如果您对TheSwiftProgrammingLanguage学习笔记和二十——类型转换感兴趣,那么这篇文章一定是您不可错过的。我们将详细讲解TheSwiftProgrammingLanguage学习
如果您对The Swift Programming Language学习笔记和二十——类型转换感兴趣,那么这篇文章一定是您不可错过的。我们将详细讲解The Swift Programming Language学习笔记的各种细节,并对二十——类型转换进行深入的分析,此外还有关于ACM International Collegiate Programming Contest, Damascus University Collegiate Programming Cont...、ACM International Collegiate Programming Contest, Egyptian Collegiate Programming Contest (ECPC 2...、ACM International Collegiate Programming Contest, JUST Collegiate Programming Contest (2018)、Aspect-Oriented Programming : Aspect-Oriented Programming with the RealProxy Class的实用技巧。
本文目录一览:- The Swift Programming Language学习笔记(二十)——类型转换(类型转换的英文)
- ACM International Collegiate Programming Contest, Damascus University Collegiate Programming Cont...
- ACM International Collegiate Programming Contest, Egyptian Collegiate Programming Contest (ECPC 2...
- ACM International Collegiate Programming Contest, JUST Collegiate Programming Contest (2018)
- Aspect-Oriented Programming : Aspect-Oriented Programming with the RealProxy Class
The Swift Programming Language学习笔记(二十)——类型转换(类型转换的英文)
- 类型转换
- 定义一个类层次作为例子
- 检查类型
- 向下转型
- Any和AnyObject的类型转换
- AnyObject类型
- Any类型
类型转换
类型转换
可以判断实例的类型,也可以将实例看做是其父类或者子类的实例。
类型转换在Swift中使用is
和as
操作符实现。这两个操作符提供了一种简单达意的方式去检查值的类型或者转换它的类型。
你也可以用它来检查一个类型是否实现了某个协议。
定义一个类层次作为例子
可以将类型转换用在类和子类的层次结构上,检查特定类实例的类型并且转换这个类实例的类型成为这个层次结构中的其他类型。
/** * 这个类为任何出现在数字媒体库的媒体项提供基础功能 */ class MediaItem { var name: String init(name: String) { self.name = name } } class Movie: MediaItem { var director: String init(name: String,director: String) { self.director = director super.init(name: name) } } class Song: MediaItem { var artist: String init(name: String,artist: String) { self.artist = artist super.init(name: name) } } let library = [ // 类型被推断为[MediaItem] Movie(name: "Casablanca",director: "Michael Curtiz"),Song(name: "Blue Suede Shoes",artist: "Elvis Presley"),Movie(name: "Citizen Kane",director: "Orson Welles"),Song(name: "The One And Only",artist: "Chesney Hawkes"),Song(name: "Never Gonna Give You Up",artist: "Rick Astley") ] print(library) // [Movie,Song,Movie,Song]
推断出[MediaItem]
类作为library
的类型。在幕后library
里存储的媒体项依然是Movie
和Song类型的。但是,若你迭代它,依次取出的实例会是
MediaItem类型的,而不是Movie
和Song
类型。为了让它们作为原本的类型工作,你需要检查它们的类型或者向下转换它们到其它类型。
检查类型
用类型检查操作符(is
)来检查一个实例是否属于特定子类型。若实例属于那个子类型,类型检查操作符返回true
,否则返回false
。
/** * 这个类为任何出现在数字媒体库的媒体项提供基础功能 */ class MediaItem { var name: String init(name: String) { self.name = name } } class Movie: MediaItem { var director: String init(name: String,Song] var movieCount = 0 var songCount = 0 for i in library { if i is Movie { ++movieCount } else if i is Song { ++songCount } } print("\(movieCount) movies,\(songCount) songs") // 2 movies,3 songs
向下转型
某类型的一个常量或变量可能在幕后实际上属于一个子类。当确定是这种情况时,你可以尝试向下转到它的子类型,用类型转换操作符(as?
或as!
)。
因为向下转型可能会失败,类型转型操作符带有两种不同形式。条件形式
(conditional form)as?
返回一个你试图向下转成的类型的可选值(optional value)。强制形式``as!
把试图向下转型和强制解包(force-unwraps)转换结果结合为一个操作。
当你不确定向下转型可以成功时,用类型转换的条件形式(as?
)。条件形式的类型转换总是返回一个可选值(optional value),并且若下转是不可能的,可选值将是nil
。这使你能够检查向下转型是否成功。
只有你可以确定向下转型一定会成功时,才使用强制形式(as!
)。当你试图向下转型为一个不正确的类型时,强制形式的类型转换会触发一个运行时错误。
转换没有真的改变实例或它的值。根本的实例保持不变;只是简单地把它作为它被转换成的类型来使用。
/** * 这个类为任何出现在数字媒体库的媒体项提供基础功能 */ class MediaItem { var name: String init(name: String) { self.name = name } } class Movie: MediaItem { var director: String init(name: String,Song] for i in library { if let item = i as? Movie { print("Movie: name = \(item.name),director = \(item.director)") } else if let item = i as? Song { print("Song: name = \(item.name),artist = \(item.artist)") } } /* Movie: name = Casablanca,director = Michael Curtiz Song: name = Blue Suede Shoes,artist = Elvis Presley Movie: name = Citizen Kane,director = Orson Welles Song: name = The One And Only,artist = Chesney Hawkes Song: name = Never Gonna Give You Up,artist = Rick Astley */
Any和AnyObject的类型转换
Swift为不确定类型提供了两种特殊的类型别名:
AnyObject
可以表示任何类类型的实例Any
可以表示任何类型,包括函数类型。
注意,只有当你确实需要它们的行为和功能时才使用Any
和AnyObject
。在你的代码里使用你期望的明确类型总是更好的。
AnyObject类型
当在工作中使用Cocoa APIs时,我们经常会接收到一个[AnyObject]
类型的数组,或者说“一个任意类型对象的数组”。这是因为Objective-C
没有明确的类型化数组。但是,你常常可以从API提供的信息来确定数组中对象的类型。
译者注
这段文档似乎没有及时更新,从Xcode 7和Swift 2.0开始,由于Objective-C引入了轻量泛型,集合类型已经可以类型化了,在Swift中使用Cocoa API也越来越少遇到AnyObject
类型了。详情请参阅Lightweight Generics
和Collection Classes
。
在这些情况下,你可以使用强制形式的类型转换(as
)来下转数组中的每一项到比AnyObject
更明确的类型,不需要可选解包(optional unwrapping)。
/** * 这个类为任何出现在数字媒体库的媒体项提供基础功能 */ class MediaItem { var name: String init(name: String) { self.name = name } } class Movie: MediaItem { var director: String init(name: String,artist: String) { self.artist = artist super.init(name: name) } } let library: [AnyObject] = [ Movie(name: "2001: A Space Odyssey",director: "Stanley Kubrick"),Movie(name: "Moon",director: "Duncan Jones"),Movie(name: "Alien",director: "Ridley Scott") ] print(library) // [Movie,Movie] // 因为知道这个数组只包含Movie 实例,你可以直接用(as!)下转并解包到非可选的Movie类型 for item in library { let movie = item as! Movie print("Movie: name = \(movie.name),director = \(movie.director)") } print("==========") // 为了变为一个更简短的形式,下转数组为[Movie]类型而不是下转数组中的每一项 for movie in library as! [Movie] { print("Movie: name = \(movie.name),director = \(movie.director)") } /* Movie: name = 2001: A Space Odyssey,director = Stanley Kubrick Movie: name = Moon,director = Duncan Jones Movie: name = Alien,director = Ridley Scott ========== Movie: name = 2001: A Space Odyssey,director = Ridley Scott */
在上面的代码中,可以下转数组中的各项,也可以直接下转整个数组,前提是实际类型是相同的。
Any类型
使用Any
类型来和混合的不同类型一起工作,包括函数类型和非类类型。
/** * 这个类为任何出现在数字媒体库的媒体项提供基础功能 */ class MediaItem { var name: String init(name: String) { self.name = name } } class Movie: MediaItem { var director: String init(name: String,director: String) { self.director = director super.init(name: name) } } var things = [Any]() things.append(0) things.append(0.0) things.append(42) things.append(3.14159) things.append("hello") things.append((3.0,5.0)) things.append(Movie(name: "Ghostbusters",director: "Ivan Reitman")) things.append({ (name: String) -> String in "Hello,\(name)" }) for thing in things { switch thing { case 0 as Int: // switch语句的case绑定它们匹配到的值到一个指定类型的常量 print("0 as Int,thing = \(thing)") case 0 as Double: // switch语句的case绑定它们匹配到的值到一个指定类型的常量 print("0 as Double,thing = \(thing)") case let i as Int: print("Int: \(i)") case let d as Double where d > 0: print("positive double = \(d),thing = \(thing)") case is Double: print("negative double,thing = \(thing)") case let s as String: print("string = \(s)") case let (x,y) as (Double,Double): print("double tuple = (\(x),\(y))") case let movie as Movie: print("movie.name = \(movie.name),director = \(movie.director)") case let c as String -> String: print("a closure: " + c("Tim")) default: print("other...,thing = \(thing)") } } /* 0 as Int,thing = 0 0 as Double,thing = 0.0 Int: 42 positive double = 3.14159,thing = 3.14159 string = hello double tuple = (3.0,5.0) movie.name = Ghostbusters,director = Ivan Reitman a closure: Hello,Tim */
ACM International Collegiate Programming Contest, Damascus University Collegiate Programming Cont...
签到题
A
4min 1Y
C
45min 3Y
题意
给两个串,要把第一个串变成第二个串。每次选择一个半径r
,然后以第一个串的中心为中心,r
为半径,左右翻转。问最少几次操作?
题解
细节有点多。
- 先是输出
-1
的情况。这个很好考虑 - 然后遍历s1串,对于位置
i
,如果需要翻转(s1[i]=s2[n+1-i]
),则打上标记1,不需要翻转(s1[i]=s2[i]
).则打上标记0,如果翻不翻转都可以(s1[i]=s1[n+1-i]
),打上标记2。 - 遍历
[1,n/2]
,对于打上标记2的位置,我们要决定是翻还是不翻,根据贪心,我们可以怠惰一点!对于打上标记2的位置,和前一个位置保持一致即可。
F
25min 1Y
题解
统计一下每个数字出现了多少次,出现了x
次,对答案的贡献则为x!
,相乘即为答案。
J
42min 2Y
题解
按题意模拟。
冷静分析一下开局
- 开场看了C觉得很基本,然后过了A,开始写C。
- C细节没考虑清楚,用了
10min
,WA on test 2!
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 100000 + 10;
int T;
char s1[N], s2[N], s3[N];
bool ok[N];
int main() {
scanf("%d", &T);
while (T --) {
scanf("%s %s", s1+1, s2+1);
int n = strlen(s1+1);
int mid = (n+1)/2;
if (s1[mid] != s2[mid]) {
printf("-1\n"); continue;
}
bool gg = 0;
for (int i=1;i<mid;i++) {
if (s1[i]==s2[i] && s1[n-i+1]==s2[n-i+1])
ok[i] = 1;
else if (s1[i]==s2[n-i+1] && s1[n-i+1]==s2[i])
ok[i] = 0;
else
gg = 1;
}
if (gg) {
printf("-1\n"); continue;
}
int ans = 0;
ok[0] = 1;
for(int i=1;i<mid;i++) {
if (ok[i] != ok[i-1])
ans ++;
}
printf("%d\n", ans);
}
}
完全没有考虑s1[i]=s1[n+1-i]
的情况。
用了6分钟fix了一下。s1[i]=s1[n+1-i]
int ans = 0;
ok[0] = 1;
for(int i=1;i<mid;i++) {
if (ok[i] != ok[i-1] && ok[i] != 2)
ans ++;
}
printf("%d\n", ans);
然后喵了个呜,又一次WA2
- 我逃跑,用了5min时间过了F
- 用了10min的时间J题
WA2
- 用了5min的时间fix了一下,人调换方向那个地方写得意识有点模糊。
- 用了2min时间fix了一下C,很沙比的错误,比如说
n = 7
,前3位,标记为0 2 0
的情况就智障掉了。
前期比较容易细节没考虑清楚就上去写代码。C
,J
这两个模拟题都是这个原因吧。开始写代码之间,大概是抱着“随便搞搞就好”的想法。这种态度很沙比的啊。
- 我在求什么?
- 在模拟的过程,变量会如何变化?
这两个问题都考虑得不清楚吧!
中档题
B
Hash的做法很容易看出。然后就unlimited WA TLE MLE
搞Hash的经验严重不足?
边的种数不会超过n种,因此我们放n个桶。每个桶记录这种边出现的次数。
然后就是对一个XXX进制下,n位数的hash了【双hash保平安】
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;
typedef long long LL;
const int N = 10000008;
const LL MOD1 = 100000007;
const LL MOD2 = 923439347;
int T;
int n, x, y;
int val[N]; vector<int> v;
LL k1[N], k2[N];
unordered_map< LL, int > mp;
int main() {
scanf("%d", &T);
k1[0] = k2[0] = 1;
for(int i=1;i<N;i++) {
k1[i]=k1[i-1]*10007LL%MOD1;
k2[i]=k2[i-1]*20007LL%MOD2;
}
while (T --) {
scanf("%d", &n);
v.clear();
for (int i = 1; i <= n; i ++) {
scanf("%d %d", &x, &y);
if (x > y) swap(x, y);
val[i] = (2*n+1)*x + y;
v.push_back(val[i]);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for(int i=1;i<=n;i++) {
val[i] = lower_bound(v.begin(), v.end(), val[i])-v.begin()+1;
}
mp.clear();
LL sum1, sum2;
LL ans=0;
for (int i=1;i<=n;i++) {
sum1 = 0, sum2 = 0;
for(int j=1;j<=n;j++) {
sum1 += k1[val[j]];
sum1 %= MOD1;
sum2 += k2[val[j]];
sum2 %= MOD2;
}
mp[sum1*MOD2 + sum2] ++;
for(int j=i+1;j<=n;j++) {
sum1 += k1[val[j]]-k1[val[j-i]];
sum1 = (sum1%MOD1+MOD1)%MOD1;
sum2 += k2[val[j]]-k2[val[j-i]];
sum2 = (sum2%MOD2+MOD2)%MOD2;
mp[sum1*MOD2+sum2] ++;
}
for (auto x: mp) {
LL v = x.second;
ans += v * (v - 1) / 2;
}
mp.clear();
}
printf("%lld\n", ans);
}
}
G
题意
修改最少的元素,使得序列的GCD为x,LCM为y。
题解
先判-1
(一番激烈的讨论)
如果a[i]%x!=0 or y%a[i]!=0
,那么i
就是个卜。
直觉告诉我们把一个数字变成x,另一个数字变成y,只要其它的数字不卜,生活就有保障了。
- 如果卜的个数>=2,那么答案就是卜的个数了。
- 否则答案可能是1,可能是2,可能是0
- 答案是0,很简单。
- 答案是1,很不简单。我们枚举一下每个数字,看他是否能力挽狂澜,我们把枚举的数字放逐掉,求出其它数字的GCD&LCM(先预处理前缀后缀GCD&LCM),然后看一看世界末日前怎么办?来得及拯救吗?【具体怎么做,留给读者思考。】
- 答案是2,很简单,加个else
I
题意
n堆石头,两种操作,两人轮流操作。
- 可以从一堆石头中拿走一个石头。
- 如果每堆石子都至少有1个,可以从每堆石头中拿走一个石头。
先手胜?后手胜?
题解
冷静分析一下
- n%2=1. 易证,留给读者思考【读者似乎就我一个人。】
- n%2=0. 这个得冷静分析一下。
- min=1, 先手可以把后手气死。类似于chomp Game的模型。
- min=2, 第一种操作肯定不可以施展的!不然会被气死。既然只能施展第二种操作,胜负显而易见了吧。
- min=3, 先手可以把后手气死。类似于chomp Game的模型。
- min=4, .......
博弈在模型的直觉很重要的吖!这题意识到了chomp Game就很简单了吧。
K
题意
n个点,n条边,多组查询,求两点间最短路。
题解
先去掉一条边edge,那么这个图就是一颗树了。
枚举,u到v是否要经过edge即可。
冷静分析一下中期
- 先用了10min施展G,施展了一大半,然后咕咕咕了。
- 先用了10min施展B题。没考虑清楚自己在hash什么东西,耽误了一段时间,然后
WA11
。 - 用了13min过了K。
- 用了3min过了G的样例,
WA2
- 开始unlimited Fix G,中间用了很长一段时间次饭去了。但调G的时间至少有1小时。
- Bug1:没读完就输出结果,WA
- Bug2:复杂度
nsqrt(n)
.【不错,有创意】 - Bug3:
n=1
的特判不到位,搞得后面越界了。一大波RE。
- 用了一个小时Fix B题的Hash,好不容易开始双hash然后MLE。枚举长度后清空,解决了问题。
- 用了半个小时搞I
emmmm....大部分时间都在Fix辣鸡。。。
考虑清楚再写啊······
羊肉粉丝汤弱鸡啊。
感觉30min
4题,2h30min
8题是比较合理的。
ACM International Collegiate Programming Contest, Egyptian Collegiate Programming Contest (ECPC 2...
A.Arcade Game(康拓展开)
题意:
给出一个每个数位都不同的数n,进行一场游戏。每次游戏将n个数的每个数位重组。如果重组后的数比原来的数大则继续游戏,否则算输。如果重组后的数是最大的数则算赢,问赢的概率。
题解:
用康拓展开求出n是第几大的数,然后递推后面的概率。


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
char s[15];
double ans;
int fac[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
double cal(char *s) {
int res = 0;
int k = strlen(s);
for(int i = 0; i < k; i++) {
int cnt = 0;
for(int j = i+1; j < k; j++) if(s[j]<s[i]) cnt++;
res += fac[k-i-1]*cnt;
}
if(res==fac[k]-1) return 0;
double ans = 1.0/fac[k];
for(int i = res; i < fac[k]-2; i++) ans += ans/fac[k];
return ans;
}
int main() {
scanf("%d", &t);
while(t--) {
scanf("%s", s);
printf("%.9lf\n", cal(s));
}
}
B.Unlucky Teacher(模拟)
题意:
Q个题目和M个学生的判卷,求出每道题的答案。如果求不出则输出?。
题解:
模拟即可。


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
int q, m;
int num[105], state[105];
char ans[105];
char s1[2], s2[2];
int main() {
scanf("%d", &t);
while(t--) {
memset(state, 0, sizeof(state));
memset(num, 0, sizeof(num));
scanf("%d%d", &q, &m);
while(m--) {
for(int i = 1; i <= q; i++) {
scanf("%s%s", s1, s2);
if(s2[0]==''T'') num[i] = -1, ans[i] = s1[0];
else {
if((num[i]==-1)||((state[i]&(1<<s1[0]-''A''))>0)) continue;
state[i] |= 1<<s1[0]-''A'';
num[i]++;
if(num[i]==3) {
for(int j = 0; j < 4; j++)
if(!(state[i]&(1<<j))) {
ans[i] = ''A''+j;
break;
}
num[i] = -1;
}
}
}
}
for(int i = 1; i <= q; i++) {
if(num[i]>-1) printf("?");
else printf("%c", ans[i]);
if(i < q) printf(" ");
}
puts("");
}
}
C.Connecting Graph(并查集+二分)
题意:
初始有n个点,m次操作。每次操作加一条边或者询问两个点第一次连通的时刻(若不连通输出-1)。
题解:
GYM - 100814 C.Connecting Graph


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int t;
int n, m;
int u, v, k;
int f[N], num[N];
vector<pair<int, int> > g[N];
vector<int> c[N];
bool check(int x) {
int l = 0, r = g[u].size()-1;
while(l <= r) {
int mid = l+r>>1;
if(g[u][mid].first <= x) l = mid+1;
else r = mid-1;
}
int p1 = g[u][r].second;
l = 0, r = g[v].size()-1;
while(l <= r) {
int mid = l+r>>1;
if(g[v][mid].first <= x) l = mid+1;
else r = mid-1;
}
int p2 = g[v][r].second;
if(p1==p2) return 1;
return 0;
}
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
num[i] = 1;
f[i] = i;
c[i].clear();
g[i].clear();
c[i].push_back(i);
g[i].push_back(make_pair(0, i));
}
for(int i = 1; i <= m; i++) {
scanf("%d%d%d", &k, &u, &v);
if(k&1) {
u = f[u]; v = f[v];
if(u!=v) {
if(num[u]>num[v]) swap(u, v);
for(int j = 0; j < num[u]; j++) {
c[v].push_back(c[u][j]);
f[c[u][j]] = v;
g[c[u][j]].push_back(make_pair(i, v));
}
num[v] += num[u];
num[u] = 0;
c[u].clear();
}
}
else {
int l = 0, r = i-1;
while(l<=r) {
int mid = l+r>>1;
if(check(mid)) r = mid-1;
else l = mid+1;
}
if(check(r+1)) printf("%d\n", r+1);
else puts("-1");
}
}
}
}
D.Frozen Rivers
题意:
一棵n个节点的树,每条边代表一条河。从点1开始边以每秒1个单位开始融化。每个点连的边(不包括连向父亲的)有一条融化完时剩下的该点连的边融化速度降为0.5。q次询问,每次询问某个时刻融化到叶子节点的数量。
题解:
设minn[u]代表节点u的边中权值最小的那个,将点u所有边的权值加上他们与minn[u]的差值。即每条边的权值翻倍再减去minn[u]。
这样处理完之后就省去了0.5的限制。问题变成了求叶子节点到根节点的距离。


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
const int inf = 0x3f3f3f3f;
int t;
int n, q, p, c;
int tot;
int head[N], to[N], nxt[N], w[N], minn[N];
int cnt;
ll tim, num[N];
void dfs(int u, ll val) {
if(minn[u]==inf) {
num[++cnt] = val;
return ;
}
for(int i = head[u]; ~i; i = nxt[i]) {
w[i] = 2*w[i]-minn[u];
dfs(to[i], val+w[i]);
}
}
int main() {
scanf("%d", &t);
while(t--) {
tot = cnt = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++) head[i] = -1, minn[i] = inf;
for(int i = 2; i <= n; i++) {
scanf("%d%d", &p, &c);
to[++tot] = i; nxt[tot] = head[p]; head[p] = tot, w[tot] = c;
minn[p] = min(minn[p], c);
}
dfs(1, 0);
sort(num+1, num+cnt+1);
scanf("%d", &q);
while(q--) {
scanf("%lld", &tim);
int ans = upper_bound(num+1, num+cnt+1, tim)-num-1;
printf("%d\n", ans);
}
}
}
E.Palmyra(dp)
题意:
给出n*m的矩阵。从点(1,1)出发,可以向右或者向下移动,最后走到(n,m)。将路途上的点值乘起来,问最后的值拿6进制表示末尾最多有几个0。
题解:
题意可以理解为,使最后2的因子数和3的因子数中的最小值最大。
dp[i][j][k]表示走到(i,j),3的因子数为k时2的因子数最多是多少。


#include <bits/stdc++.h>
using namespace std;
int t;
int n, m;
int q[105][105][3];
int dp[105][105][1505];
int main() {
scanf("%d", &t);
while(t--) {
memset(q, 0, sizeof(q));
memset(dp, -1, sizeof(dp));
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
scanf("%d", &q[i][j][0]);
int t = q[i][j][0];
while(t%2 == 0) {
q[i][j][1]++;
t /= 2;
}
while(t%3 == 0) {
q[i][j][2]++;
t /= 3;
}
}
}
dp[1][1][q[1][1][2]] = q[1][1][1];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
int n2 = q[i][j][1];
int n3 = q[i][j][2];
for(int k = 0; k + n3 <= 1500; k++) {
if(dp[i][j-1][k] != -1)
dp[i][j][k+n3] = max(dp[i][j][k+n3], dp[i][j-1][k]+n2);
if(dp[i-1][j][k] != -1)
dp[i][j][k+n3] = max(dp[i][j][k+n3], dp[i-1][j][k]+n2);
}
}
}
int ans = 0;
for(int i = 1; i <= 1500; i++) {
int nn = min(dp[n][m][i], i);
ans = max(ans, nn);
}
printf("%d\n", ans);
}
return 0;
}
F.Geometry
题意:
给出长和宽,判断时正方形还是矩形。
题解:
判断w是否等于h。


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
int w, h;
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d%d", &w, &h);
if(w==h) puts("Square");
else puts("Rectangle");
}
}
G.It is all about wisdom(最短路+二分)
题意:
给出一个图,图中的每条边有使用的最低限制值和花费。问从1走到n在总花费小于k的前提下的最小限制值是多少。
题解:
标准的二分套最短路的题型。二分最小的限制值即可。


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
const int inf = 0x3f3f3f3f;
int t;
int n, m, k;
int u, v, c, l, r;
int vis[N], dis[N];
struct node {
int to, v, lim;
node(int a, int b, int c) {
to = a; v = b; lim = c;
}
};
vector<node> g[N];
bool check(int x) {
queue<int> q;
for(int i = 1; i <= n; i++) vis[i] = 0, dis[i] = inf;
q.push(1);
vis[1] = 1;
dis[1] = 0;
while(!q.empty()) {
int v = q.front();
q.pop();
vis[v] = 0;
int len = g[v].size();
for(int i = 0; i < len; i++) {
if(g[v][i].lim > x) continue;
if(g[v][i].v+dis[v] < dis[g[v][i].to]) {
dis[g[v][i].to] = g[v][i].v+dis[v];
if(!vis[g[v][i].to]) {
q.push(g[v][i].to);
vis[g[v][i].to] = 1;
}
}
}
}
if(dis[n] < k) return 1;
return 0;
}
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d%d%d", &n, &m, &k);
r = 0;
for(int i = 1; i <= n; i++) g[i].clear();
while(m--) {
scanf("%d%d%d%d", &u, &v, &c, &l);
g[u].push_back(node(v, c, l));
g[v].push_back(node(u, c, l));
r = max(r, l);
}
l = 1;
while(l<=r) {
int mid = l+r>>1;
if(check(mid)) r = mid-1;
else l = mid+1;
}
if(check(r+1)) printf("%d\n", r+1);
else puts("-1");
}
}
I.Salem
题意:
给出n个数,求数对中最大的hamming距离。
题解:
每两个数求一下异或之后二进制下1个数量即可,输出最大值。


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t, n;
int a[105];
int main() {
scanf("%d", &t);
while(t--) {
int ans = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
for(int j = 1; j < i; j++) {
int p = a[i]^a[j], cnt = 0;
for(int k = 20; k >= 0; k--) {
if(p&(1<<k)) cnt++;
}
ans = max(ans, cnt);
}
}
printf("%d\n", ans);
}
}
J.Game
题意:
给出合并规则表。两个人轮流进行操作,每次选择从最左面或者最右面开始每两个合并成一个。如果最后剩的是元音字符,就是Salah获胜。否则Marzo获胜。
题解:
暴力维护每一种情况。用1表示S获胜,0表示M获胜。
当S操作时,若两种情况存在1,则当前为1。
当M操作时,若两种情况存在0,则当前为0。


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4+10;
int t;
int tot;
int len[N];
char s[N][N];
char g[30][30];
char cmp[5] = {''a'', ''e'', ''i'', ''o'', ''u''};
bool dfs(int num, int k) {
if(len[num] < 3) {
char c;
if(len[num]==1) c = s[num][0];
else c = g[s[num][0]-''a''][s[num][1]-''a''];
for(int i = 0; i < 5; i++) if(c==cmp[i]) return true;
return false;
}
++tot;
for(int i = 0; i < len[num]; i+=2) {
if(i==len[num]-1) s[tot][i/2] = s[num][i];
else s[tot][i/2] = g[s[num][i]-''a''][s[num][i+1]-''a''];
}
len[tot] = (len[num]+1)/2;
bool res = dfs(tot, k^1);
if(len[num]&1) {
++tot;
s[tot][0] = s[num][0];
for(int i = 1; i < len[num]; i+=2) {
s[tot][i/2+1] = g[s[num][i]-''a''][s[num][i+1]-''a''];
}
len[tot] = (len[num]+1)/2;
if(k) res &= dfs(tot, k^1);
else res |= dfs(tot, k^1);
}
return res;
}
int main() {
scanf("%d", &t);
while(t--) {
tot = 0;
for(int i = 0; i < 26; i++) scanf("%s", g[i]);
scanf("%s", s[0]);
len[0] = strlen(s[0]);
if(dfs(0, 0)) puts("Salah");
else puts("Marzo");
}
}
K.PhD math
题意:
给出a,b,n,p(a<b)。求a/b的前n位数中有多少字串整除p。
题解:
从1扫到n。维护每一位新增的余数。


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
int t;
ll a, b;
int n, p;
int bit[N];
int v1[205], v2[205];
ll ans;
int main() {
scanf("%d", &t);
while(t--) {
ans = 0;
memset(v1, 0, sizeof(v1));
memset(v2, 0, sizeof(v2));
scanf("%lld%lld%d%d", &a, &b, &n, &p);
for(int i = 1; i <= n; i++) {
a *= 10;
bit[i] = a/b;
a = a%b;
}
for(int i = 1; i <= n; i++) {
for(int j = 0; j < p; j++) {
if(i&1) v1[j] = 0;
else v2[j] = 0;
}
for(int j = 0; j < p; j++) {
if(i&1) v1[(j*10+bit[i])%p] += v2[j];
else v2[(j*10+bit[i])%p] += v1[j];
}
if(i&1) v1[bit[i]%p]++, ans += v1[0];
else v2[bit[i]%p]++, ans += v2[0];
}
printf("%lld\n", ans);
}
}
L.Candy Jars(博弈)
题意:
N个罐子,每个罐子有一定数量的糖。两个人轮流操作,每次选定一罐,把其他罐中的糖都扔掉。然后把选定罐中的糖任意分配给每个罐,但要保证每个罐中都有糖。不能操作者判输。
题解:
只要有一个罐子糖数必胜则操作者必胜。
当所有罐子糖数小于N时无法给所有罐子分配糖,必输。
当存在罐子糖数在[N,N(N-1)]时,可以把糖分成必输态,即分成所有罐子糖数小于N的状态,这时必胜。
然后举例发现N(N-1)是一个循环节,取模就可以了。


#include <bits/stdc++.h>
using namespace std;
int t, n;
int k;
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
int ans = 0;
for(int i = 1; i <= n; i++) {
scanf("%d", &k);
k %= n*(n-1);
if(k==0 || k > n-1) ans = 1;
}
if(ans) puts("Alice");
else puts("Bob");
}
}
M.Building Force Fields(dp)
题意:
按x升序给出n个点的二维坐标,并保证没有两个点x坐标相同。可以在任意两个点之间连边,最后要保证每个点都在连边之下(或在连边上)。问最小的连边总长。
题解:
dp[i]表示第i个点结尾的最小总连边长。
转移是枚举i向第j(1<=j<i)个点连边,要保证连边上方无点。即第i和第j个点的斜率比第i个点和(j,i)范围内的点的斜率都小。最后取最小值。


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t, n;
double dp[1005];
struct node {
ll x, y;
}a[1005];
double dis(int n1, int n2) {
return sqrt((a[n1].x-a[n2].x)*(a[n1].x-a[n2].x)+(a[n1].y-a[n2].y)*(a[n1].y-a[n2].y));
}
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%lld%lld", &a[i].x, &a[i].y);
dp[1] = dis(1, 2);
for(int i = 2; i <= n; i++) {
int pos = i-1;
dp[i] = min(dp[i-2], dp[i-1])+dis(i, i-1);
for(int j = i-2; j >= 1; j--) {
if((a[i].y-a[pos].y)*(a[i].x-a[j].x) >= (a[i].y-a[j].y)*(a[i].x-a[pos].x)) {
dp[i] = min(dp[i], min(dp[j-1], dp[j])+dis(i, j));
pos = j;
}
}
}
printf("%.6lf\n", dp[n]);
}
}
ACM International Collegiate Programming Contest, JUST Collegiate Programming Contest (2018)
ACM International Collegiate Programming Contest, JUST Collegiate Programming Contest (2018)
B. New Assignment
- 有 n 个人 (1 ≤ n ≤ 104),有男有女,每个人都有一个 id,现在这 n 个人分成学习互助小组,有三种组队模式,一个男人一组,一个女人一组,一男一女一组,如果要一男一女一组,那么这两人 id 的 gcd 要 > 1。保证任意三个人的 gcd=1。求小组的组数最少是多少?
- 看起来是一个很裸的二分匹配,当两个人性别为男女,并且 gcd>1 时,连边。可是这里的连边的时候复杂度很高。直接暴力连边为 5000 × 5000×log 级别的。所以,需要换一个角度考虑。
- 可以发现,由于任意三个数的 gcd=1 的性质,可以保证任何一个质因子最多有两个被除数。当且仅当这两个被除数的性别不同连边。
#include"stdio.h"
#include"string.h"
#include"queue"
#include"vector"
#include"algorithm"
#include"iostream"
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=100010;//点数
const int maxm=400010;//边数
struct node{
int v,next,cap,flow;
}edge[maxm];
int cnt;
int head[maxn];
int cur[maxn],d[maxn];// 当前弧下标 结点到汇点弧长
int p[maxn],gap[maxn];////可增广路上的上一条弧 gap优化
int ss[maxn];//保存路径
void init(){
cnt=-1;
memset(head,-1,sizeof(head));
}
void debug(int k){
int i,j;
printf("\n");
for (i=0;i<=k;i++)
for (j=head[i];j!=-1;j=edge[j].next)
printf("%d %d %d\n",i,edge[j].v,edge[j].flow);
}
void add(int u,int v,int w,int rw=0){
cnt++;
edge[cnt].v=v;
edge[cnt].next=head[u];
edge[cnt].cap=w;
edge[cnt].flow=0;
head[u]=cnt;
cnt++;
edge[cnt].v=u;
edge[cnt].next=head[v];
edge[cnt].cap=rw;
edge[cnt].flow=0;
head[v]=cnt;
}
void bfs(int k){
int v,i;
int u;
memset(gap,0,sizeof(gap));
memset(d,-1,sizeof(d));
d[k]=0;
gap[0]++;
queue<int> q;
q.push(k);
while(q.empty()==false){
u=q.front();q.pop();
for (i=head[u];i!=-1;i=edge[i].next){
v=edge[i].v;
if (d[v]==-1) {
d[v]=d[u]+1;
gap[d[v]]++;
q.push(v);
}
}
}
}
int sap(int s,int t,int N){
int i;
bfs(t);
memcpy(cur,head,sizeof(head));
int top=0;
int u=s;
int ans=0;
while(d[s]<N){
if (u==t){
int min=inf;
int inser;
for (i=0;i<top;i++){
if (min>=edge[ss[i]].cap-edge[ss[i]].flow){
min=edge[ss[i]].cap-edge[ss[i]].flow;
inser=i;//这跟管子是满流了
}
}
for (i=0;i<top;i++){
edge[ss[i]].flow+=min;
edge[ss[i]^1].flow-=min;
}
ans+=min;
top=inser;
u=edge[ss[top]^1].v;//u为满流的那个结点 也就是那根管子的倒管子的终点
continue;
}
bool ok=false;
int v;
for (i=cur[u];i!=-1;i=edge[i].next){
v=edge[i].v;
if (edge[i].cap-edge[i].flow>0&&d[v]+1==d[u]){
ok=true;
cur[u]=i;
break;
}//u后 添加了一条下标为i的弧
}
if(ok==true){
ss[top]=cur[u];
top++;
u=v;
continue;
}
//如果这条路已经走不通了,那么撤退
int min=N;
for (i=head[u];i!=-1;i=edge[i].next)
if (edge[i].cap-edge[i].flow>0&&d[edge[i].v]<min){
min=d[edge[i].v];
cur[u]=i;
}
gap[d[u]]--;
if (gap[d[u]]==0) return ans;
d[u]=min+1;
gap[d[u]]++;
if (u!=s) {
top--;
u=edge[ss[top]^1].v;
}
}
return ans;
}
int gcd(int a,int b){
if (a%b==0) return b;
return gcd(b,a%b);
}
int prime[600000]={0},numprime=0;
bool isNotPrime[1000010]={1,1};
void sushu(int N){
long long int i;
for (i=2;i<=N;i++) {
if(! isNotPrime[i])
prime[numprime ++]=i;
for(long j = 0 ; j < numprime && i * prime[j] < N ; j ++)
{
isNotPrime[i * prime[j]] = 1;
if( !(i % prime[j] ) )
break;
}
}
}
int a[10500];
char s[10];
vector<int > v[1000005];
int vis[1000005];
int main(){
int e,t,i,j,x,y,cap,now;
int n,m;
sushu(1000000);
scanf("%d",&t);
for (e=1;e<=t;e++){
memset(vis,0,sizeof(vis));
for (i=0;i<numprime;i++) v[prime[i]].clear();
init();
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
for (j=1;j<=n;j++) {
scanf("%s",s);
if (s[0]==''M'') {
now=a[j];
for (i=0;i<numprime&&prime[i]<=1000;i++) {
// printf("%d\n",now);
if (now%prime[i]==0) v[prime[i]].push_back(j);
while (now%prime[i]==0) now=now/prime[i];
if (now==1||isNotPrime[now]==0) break;
}
if (isNotPrime[now]==0) v[now].push_back(j);
} else {
now=a[j];
for (i=0;i<numprime&&prime[i]<=1000;i++) {
if (now%prime[i]==0) v[prime[i]].push_back(-j);
while (now%prime[i]==0) now=now/prime[i];
if (now==1||isNotPrime[now]==0) break;
}
if (isNotPrime[now]==0) v[now].push_back(-j);
}
}
// printf("%d %d %d\n",prime[0],v[prime[0]][0],v[prime[0]][1]);
for (i=0;i<numprime;i++)
if (v[prime[i]].size()==2&&v[prime[i]][0]*v[prime[i]][1]<0) {
if (v[prime[i]][0]>0) {
if (vis[v[prime[i]][0]]==0) {add(0,v[prime[i]][0],1);vis[v[prime[i]][0]]=1;}
if (vis[-v[prime[i]][1]]==0) {add(-v[prime[i]][1],n+1,1);vis[-v[prime[i]][1]]=1;}
add(v[prime[i]][0],-v[prime[i]][1],inf);
// printf("%d %d\n",v[prime[i]][0],-v[prime[i]][1]);
}
else {
if (vis[v[prime[i]][1]]==0) {add(0,v[prime[i]][1],1);vis[v[prime[i]][1]]=1;}
if (vis[-v[prime[i]][0]]==0) {add(-v[prime[i]][0],n+1,1);vis[-v[prime[i]][0]]=1;}
add(v[prime[i]][1],-v[prime[i]][0],inf);
// printf("%d %d\n",v[prime[i]][1],-v[prime[i]][0]);
}
}
int ans=sap(0,n+1,n+2);
printf("%d\n",n-ans);
}
}
E. Maximum Sum
- 取数问题。16*16 的矩阵,如果你取了这个数,那么周围 8 个格子的数都不能取。求取的数和最大。
- dp 瞎搞。事先筛选出行内任意两个相邻位置不同的状态,大约有 3000 种不到。
- dp [i][j] 代表第 i 行,这一行的取数方案为 j 时,前 i 行的最大和。由于第 i-1 行无法去影响 i+1 行,故可以这样设置状态。
- 考虑转移, 设上一行的状态为 k, 当前行的状态为 j,如果 j and k==0 并且 j<<1 and k ==0 并且 j and k<<1 ==0 那么表示可以转移。
- 尽管算下来是超高的复杂度,不过千万不要低估银河评测机的实力。
#include"stdio.h"
#include"string.h"
#include"vector"
#include"algorithm"
using namespace std;
vector<int> v;
int d[20];
int a[50][50];
int dp[17][2600];
int main(){
int i,j,k,l;
int e,t,n;
int ans,x;
int tmp;
d[0]=1;
v.clear();
for (i=1;i<=17;i++) d[i]=d[i-1]*2;
for (i=0;i<=d[16]-1;i++) {
int sign=0;
for (j=0;j<=14;j++)
if ((i&d[j])>0&&(i&d[j+1])>0) {sign=1;break;}
if (sign==0) v.push_back(i);
}
l=v.size();
scanf("%d",&t);
for (e=1;e<=t;e++) {
scanf("%d",&n);
for (i=1;i<=n;i++)
for (j=1;j<=n;j++) scanf("%d",&a[i][j]);
memset(dp,0,sizeof(dp));
for (i=0;i<l&&v[i]<=d[n]-1;i++) {
for (j=1;j<=n;j++) if ((v[i]&d[j-1])>0) dp[1][i]+=a[1][j];
// printf("%d :%d\n",i,dp[1][v[i]]);
}
for (k=2;k<=n;k++) {
for (i=0;i<l&&v[i]<=d[n]-1;i++) {
int tmp=0;
for (x=1;x<=n;x++) if ((v[i]&d[x-1])>0) tmp+=a[k][x];
for (j=0;j<l&&v[j]<=d[n]-1;j++)
if ((v[i]&v[j])==0&&((v[i]<<1)&v[j])==0&&(v[i]&(v[j]<<1))==0) {
dp[k][i]=max(dp[k][i],tmp+dp[k-1][j]);
// printf("%d :%d :%d\n",k,v[i],dp[k][v[i]]);
}
}
}
ans=0;
for (i=0;i<l&&v[i]<=d[n]-1;i++) ans=max(dp[n][i],ans);
printf("%d\n",ans);
}
}
Aspect-Oriented Programming : Aspect-Oriented Programming with the RealProxy Class
Aspect-Oriented Programming : Aspect-Oriented Programming with the RealProxy Class
A well-architected application has separate layers so different concerns don’t interact more than needed. Imagine you’re designing a loosely coupled and maintainable application,but in the middle of the development,you see some requirements that might not fit well in the architecture,such as:
- The application must have an authentication system,used before any query or update.
- The data must be validated before it’s written to the database.
- The application must have auditing and logging for sensible operations.
- The application must maintain a debugging log to check if operations are OK.
- Some operations must have their performance measured to see if they’re in the desired range.
Any of these requirements need a lot of work and,more than that,code duplication. You have to add the same code in many parts of the system,which goes against the “don’t repeat yourself” (DRY) principle and makes maintenance more difficult. Any requirement change causes a massive change in the program. When I have to add something like that in my applications,I think,“Why can’t the compiler add this repeated code in multiple places for me?” or,“I wish I had some option to ‘Add logging to this method.’”
The good news is that something like that does exist: aspect-oriented programming (AOP). It separates general code from aspects that cross the boundaries of an object or a layer. For example,the application log isn’t tied to any application layer. It applies to the whole program and should be present everywhere. That’s called a crosscutting concern.
AOP is,according to Wikipedia,“a programming paradigm that aims to increase modularity by allowing the separation of crosscutting concerns.” It deals with functionality that occurs in multiple parts of the system and separates it from the core of the application,thus improving separation of concerns while avoiding duplication of code and coupling.
In this article,I’ll explain the basics of AOP and then detail how to make it easier by using a dynamic proxy via the Microsoft .NET Framework class RealProxy.
今天关于The Swift Programming Language学习笔记和二十——类型转换的分享就到这里,希望大家有所收获,若想了解更多关于ACM International Collegiate Programming Contest, Damascus University Collegiate Programming Cont...、ACM International Collegiate Programming Contest, Egyptian Collegiate Programming Contest (ECPC 2...、ACM International Collegiate Programming Contest, JUST Collegiate Programming Contest (2018)、Aspect-Oriented Programming : Aspect-Oriented Programming with the RealProxy Class等相关知识,可以在本站进行查询。
本文标签: