如果您对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学习笔记(二十四)——泛型(swift中泛型)
- 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学习笔记(二十四)——泛型(swift中泛型)
- 泛型
- 泛型所解决的问题
- 泛型函数
- 类型参数
- 命名类型参数
- 泛型类型
- 扩展一个泛型类型
- 类型约束
- 类型约束语法
- 类型约束实践
- 关联类型
- 关联类型实践
- 通过扩展一个存在的类型来指定关联类型
- where子句
泛型
泛型代码可以让你编写适用自定义需求以及任意类型的灵活可重用的函数和类型。它的可以让你避免重复的代码,用一种清晰和抽象的方式来表达代码的意图。
泛型
是Swift的强大特性之一,许多Swift标准库
是通过泛型代码构建的。事实上,泛型的使用贯穿了整本语言手册,只是你可能没有发现而已。例如,Swift的Array
和Dictionary
都是泛型集合。你可以创建一个Int
数组,也可创建一个String
数组,甚至可以是任意其他Swift
类型的数组。同样的,你也可以创建存储任意指定类型的字典。
泛型所解决的问题
func swapTwoInts(inout a: Int,inout _ b: Int) { let temp = a a = b b = temp } var x = 10 var y = 20 swapTwoInts(&x,&y) print(x) print(y) func swapTwodoubles(inout a: Double,inout _ b: Double) { let temp = a a = b b = temp } var m = 1.2 var n = 2.3 swapTwodoubles(&m,&n) print(m) print(n) func swapTwoStrings(inout a: String,inout _ b: String) { let temp = a a = b b = temp } var p = "aaaa" var q = "bbbb" swapTwoStrings(&p,&q) print(p) print(q)
在上面三个函数中,a
和b
类型相同。如果a
和b
类型不同,那它们俩就不能互换值。Swift是类型安全的语言,所以它不允许一个String
类型的变量和一个Double
类型的变量互换值。试图这样做将导致编译错误。
泛型函数
泛型函数可以适用于任何类型。
func swapTwovalues<T>(inout a: T,inout _ b: T) { let tempA = a a = b b = tempA } var x = 1 var y = 2 swapTwovalues(&x,&y) print(x) print(y) var m = "Hello" var n = "World" swapTwovalues(&m,&n) print(m) print(n) swap(&m,&n) // 调用Swift标准库中的泛型函数 print(m) print(n)
这个函数的泛型版本使用了占位类型名
(在这里用字母T
来表示)来代替实际类型名(例如Int
、String
或Double
)。占位类型名没有指明T
必须是什么类型,但是它指明了a
和b
必须是同一类型T
,而无论T
代表什么类型。只有swapTwovalues(_:_:)
函数在调用时,才能根据所传入的实际类型决定T
所代表的类型。
另外一个不同之处在于这个泛型函数名后面跟着占位类型名(T
),而且是用尖括号括起来的(<T>
)。这个尖括号告诉Swift
那个T
是swapTwovalues(_:_:)
函数定义的一个占位类型名,因此Swift
不会去查找名为`T“的实际类型。
上面定义的swapTwovalues(_:_:)
函数是受swap(_:_:)
函数启发而实现的。后者存在于Swift标准库
,你可以在你的应用程序中使用它。如果你在代码中需要类似swapTwovalues(_:_:)
函数的功能,你可以使用已存在的swap(_:_:)
函数。
类型参数
一旦一个类型参数被指定,你可以用它来定义一个函数的参数类型(例如swapTwovalues(_:_:)
函数中的参数a
和b
),或者作为函数的返回类型,还可以用作函数主体中的注释类型。在这些情况下,类型参数会在函数调用时被实际类型所替换。可提供多个类型参数,将它们都写在尖括号中,用逗号分开。
命名类型参数
在大多数情况下,类型参数具有一个描述性名字,例如Dictionary<Key,Value>
中的Key
和Value
,以及Array<Element>
中的Element
,这可以告诉阅读代码的人这些类型参数和泛型函数之间的关系。然而,当它们之间的关系没有意义时,通常使用单一的字母来命名,例如T
、U
、V
。
注意,请始终使用大写字母开头的驼峰式命名法(例如T
和MyTypeParameter
)来为类型参数命名,以表明它们是占位类型,而不是一个值。
泛型类型
除了泛型函数,Swift还允许你定义泛型类型
。这些自定义类、结构体和枚举可以适用于任何类型,如同Array
和Dictionary
的用法。
栈是一系列值的有序集合,和Array
类似,但它相比Swift的Array
类型有更多的操作限制。数组允许对其中任意位置的元素执行插入或删除操作。而栈,只允许在集合的末端添加新的元素(称之为入栈
)。同样的,栈也只能从末端移除元素(称之为出栈
)。
注意,栈的概念已被UINavigationController
类用来模拟视图控制器的导航结构。你通过调用UINavigationController
的pushViewController(_:animated:)
方法来添加新的视图控制器到导航栈,通过popViewControllerAnimated(_:)
方法来从导航栈中移除某个视图控制器。每当你需要一个严格的“后进先出”方式来管理集合,栈都是最实用的模型。
struct IntStack { var items = [Int]() mutating func push(item: Int) { items.append(item) } mutating func pop() -> Int { return items.removeLast() } } struct Stack<Element> { var items = [Element]() mutating func push(item: Element) { items.append(item) } mutating func pop() -> Element { return items.removeLast() } } var s = Stack<String>() s.push("abc") s.push("def") s.push("ghi") s.push("jkl") let a = s.pop() print(a)
扩展一个泛型类型
当你扩展一个泛型类型的时候,你并不需要在扩展的定义中提供类型参数列表。更加方便的是,原始类型定义中声明的类型参数列表在扩展中可以直接使用,并且这些来自原始类型中的参数名称会被用作原始定义中类型参数的引用。
struct Stack<Element> { var items = [Element]() mutating func push(item: Element) { items.append(item) } mutating func pop() -> Element { return items.removeLast() } } /** * 这个扩展并没有定义一个类型参数列表。相反的,Stack类型已有的类型参数名称Element,被用在扩展中来表示计算型属性topItem的可选类型。 */ extension Stack { var topItem: Element? { return items.isEmpty ? nil : items[items.count - 1] } } var s = Stack<String>() s.push("abc") s.push("def") s.push("ghi") s.push("jkl") if let item = s.topItem { // 可选绑定 print(item) }
类型约束
有的时候如果能将使用在泛型函数
和泛型类型
中的类型,强制约束为某种特定类型,将会是非常有用的。类型约束可以指定一个类型参数必须继承自指定类,或者符合一个特定的协议或协议组合。
例如,Swift的Dictionary
类型对字典的键的类型做了些限制。在字典的描述中,字典的键的类型必须是可哈希的。也就是说,必须有一种方法能作为其唯一的表示。Dictionary
之所以需要其键是可哈希的,是为了便于检查字典是否已经包含某个特定键的值。如无此要求,Dictionary
将无法判断是否可以插入或者替换某个指定键的值,也不能查找到已经存储在字典中的指定键的值。
这个要求强制加上了一个类型约束作用于Dictionary的键类型上,其键类型必须符合
Hashable协议,这是Swift标准库中定义的一个特定协议。***所有的Swift基本类型(例如
String、
Int、
Double和
Bool`)默认都是可哈希的*。
当你创建自定义泛型类型时,你可以定义你自己的类型约束,这些约束将提供更为强大的泛型编程能力。抽象概念,例如可哈希的,描述的是类型在概念上的特征,而不是它们的显式类型。
类型约束语法
可以在一个类型参数名后面放置一个类名或者协议名,通过冒号分隔,从而定义类型约束,它们将作为类型参数列表的一部分。这种基本的类型约束作用于泛型函数时的语法如下所示(作用于泛型类型时的语法与之相同)。
func someFunction<T: SomeClass,U: SomeProtocol>(someT: T,someU: U) { // 这里是泛型函数的函数体部分 }
类型约束实践
func findStringIndex(array: [String],_ valuetoFind: String) -> Int? { for (index,value) in array.enumerate() { if value == valuetoFind { return index } } return nil } let s = ["a","b","c"] if let i = findStringIndex(s,"b") { print("index = \(i)") } else { print("not found") } func findindex<T: Equatable>(array: [T],_ valuetoFind: T) -> Int? { for (index,value) in array.enumerate() { if value == valuetoFind { // 不加: Equatable会报错:error: binary operator '==' cannot be applied to two 'T' operands return index } } return nil } print(findindex([1.1,2.2,3.3],4.4)) // nil print(findindex(["11","22","333"],"333")!) // 2
在上面的代码中,不加: Equatable
会报错:error: binary operator '==' cannot be applied to two 'T' operands
不是所有的Swift类型都可以用等式符(==
)进行比较。例如,如果你创建一个你自己的类或结构体来表示一个复杂的数据模型,那么Swift无法猜到对于这个类或结构体而言“相等”意味着什么。正因如此,这部分代码无法保证适用于每个可能的类型T
,当你试图编译这部分代码时会出现相应的错误。
不过,所有的这些并不会让我们无从下手。Swift标准库中定义了一个Equatable
协议,该协议要求任何符合该协议的类型必须实现等式符(==
),从而能对符合该协议的类型的任意两个值进行比较。所有的Swift标准类型自动支持Equatable
协议。
加了: Equatable
之后,任何Equatable
类型都可以安全地使用在findindex(_:_:)
函数中,因为其保证支持等式操作符。
关联类型
定义一个协议时,有的时候声明一个或多个关联类型作为协议定义的一部分将会非常有用。关联类型作为协议的一部分,为某个类型提供了一个占位名(或者说别名),其代表的实际类型在协议被采纳时才会被指定。你可以通过typealias
关键字来指定关联类型。
关联类型实践
protocol Container { typealias ItemType // Container协议需要在不知道容器中元素的具体类型的情况下引用这种类型,因此声明了一个关联类型ItemType,这个协议无法定义ItemType是什么类型的别名,这个信息将留给采纳协议的类型来提供。 mutating func append(item: ItemType) var count: Int { get } subscript(i: Int) -> ItemType { get } } struct IntStack2: Container { var items = [Int]() mutating func push(item: Int) { items.append(item) } mutating func pop() -> Int { return items.removeLast() } // 遵循的Container协议的实现部分 typealias ItemType = Int // IntStack指定ItemType为Int类型,将Container协议中抽象的ItemType类型转换为具体的Int类型。 mutating func append(item: Int) { self.push(item) } var count: Int { return items.count } subscript(i: Int) -> Int { return items[i] } } /** * 由于Swift的类型推断,你实际上不用在IntStack的定义中声明ItemType为Int。因为IntStack符合Container协议的所有要求,Swift 只需通过append(_:)方法的item参数类型和下标返回值的类型,就可以推断出ItemType的具体类型。事实上,如果你在上面的代码中删除了typealias ItemType = Int这一行,这一切仍旧可以正常工作,因为Swift清楚地知道ItemType应该是何种类型。 */ struct IntStack: Container { var items = [Int]() mutating func push(item: Int) { items.append(item) } mutating func pop() -> Int { return items.removeLast() } // 遵循的Container协议的实现部分 // typealias ItemType = Int // IntStack指定ItemType为Int类型,将Container协议中抽象的ItemType类型转换为具体的Int类型。 mutating func append(item: Int) { self.push(item) } var count: Int { return items.count } subscript(i: Int) -> Int { return items[i] } } /** * 泛型版本的遵循了Container协议的Stack。 * 占位类型参数Element被用作append(_:)方法的item参数和下标的返回类型。Swift可以据此推断出Element的类型即是ItemType的类型。 */ struct Stack<Element>: Container { var items = [Element]() mutating func push(item: Element) { items.append(item) } mutating func pop() -> Element { return items.removeLast() } mutating func append(item: Element) { self.push(item) } var count: Int { return items.count } subscript(i:Int) -> Element { return items[i] } }
由于Swift的类型推断,你实际上不用在IntStack
的定义中声明ItemType
为Int
。因为IntStack
符合Container
协议的所有要求,Swift只需通过append(_:)
方法的item
参数类型和下标返回值的类型,就可以推断出ItemType
的具体类型。事实上,如果你在上面的代码中删除了typealias ItemType = Int
这一行,这一切仍旧可以正常工作,因为Swift清楚地知道ItemType
应该是何种类型。
而在泛型类型Stack
中,占位类型参数Element
被用作append(_:)
方法的item
参数和下标的返回类型。Swift可以据此推断出Element
的类型即是ItemType
的类型。
通过扩展一个存在的类型来指定关联类型
extension Array: Container {}
Swift的Array
已经提供append(_:)
方法,一个count
属性,以及一个接受Int
型索引值的可用来检索数组元素的下标。这三个功能都符合Container
协议的要求,也就意味着你可以扩展Array
去符合Container
协议,只需简单地声明Array
采纳该协议即可。你可以通过一个空扩展来实现这点。
Array
的append(_:)
方法和下标确保了Swift 可以推断出ItemType
的类型。定义了这个扩展后,你可以将任意Array
当作Container
来使用。
where子句
为关联类型定义约束也是非常有用的。你可以在参数列表中通过where
子句为关联类型定义约束。一个where
子句能够使一个关联类型符合某个特定的协议,以及某个特定的类型参数和关联类型必须类型相同。你可以通过将where
关键字紧跟在类型参数列表后面来定义where
子句,where
子句后跟一个或者多个针对关联类型的约束,以及一个或多个类型参数和关联类型间的相等关系。
protocol Container { typealias ItemType mutating func append(item: ItemType) var count: Int { get } subscript(i: Int) -> ItemType { get } } struct Stack<Element>: Container { var items = [Element]() mutating func push(item: Element) { items.append(item) } mutating func pop() -> Element { return items.removeLast() } mutating func append(item: Element) { self.push(item) } var count: Int { return items.count } subscript(i:Int) -> Element { return items[i] } } extension Array: Container {} /** * 被检查的两个Container可以不是相同类型的容器(虽然它们可以相同),但它们必须拥有相同类型的元素。这个要求通过一个类型约束以及一个where子句来表示 */ func allItemsMatch<C1: Container,C2: Container where C1.ItemType == C2.ItemType,C1.ItemType: Equatable>(aContainer: C1,_ bContainer: C2) -> Bool { if aContainer.count != bContainer.count { return false } for i in 0..<aContainer.count { if aContainer[i] != bContainer[i] { return false } } return true } let arr = ["abc","def","ghi"] var s = Stack<String>() s.append("abc") s.append("def") s.append("ghi") print(allItemsMatch(arr,s)) // true
即使栈和数组是不同的类型,但它们都符合Container
协议,而且它们都包含相同类型的值。因此你可以用这两个容器作为参数来调用allItemsMatch(_:_:)
函数。
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的相关信息,可以在本站进行搜索。
本文标签: