在本文中，您将会了解到关于TheSwiftProgrammingLanguage学习笔记的新资讯，同时我们还将为您解释二十一——嵌套类型的相关在本文中，我们将带你探索TheSwiftProgrammi
在本文中，您将会了解到关于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学习笔记（二十一）——嵌套类型（嵌套类的作用）
- 嵌套类型
- 嵌套类型实践
- 引用嵌套类型
嵌套类型
枚举常被用于为特定类或结构体实现某些功能。类似地，也能够在某个复杂的类型中，方便地定义工具类或结构体来使用。为了实现这种功能，Swift允许你定义嵌套类型，可以在支持的类型中定义嵌套的枚举、类和结构体。
要在一个类型中嵌套另一个类型，将嵌套类型的定义写在其外部类型的{}内，而且可以根据需要定义多级嵌套。
嵌套类型实践
/** * 一个结构体BlackjackCard（二十一点），用来模拟BlackjackCard中的扑克牌点数。在BlackjackCard中，Ace牌的面值可以是1或者11。 */ @H_301_32@struct BlackjackCard { @H_301_32@enum Suit: Character { @H_301_32@case Spades = "♠" @H_301_32@case Hearts = "♡" @H_301_32@case Diamonds = "♢" @H_301_32@case Clubs = "♣" } @H_301_32@enum Rank: Int { @H_301_32@case Two = 2,Three,Four,Five,Six,Seven,Eight,Nine,Ten @H_301_32@case Jack,Queen,King,Ace @H_301_32@struct Values { @H_301_32@let first: Int @H_301_32@let second: Int? } @H_301_32@var values: Values { @H_301_32@switch self { @H_301_32@case .Ace: @H_301_32@return Values(first: 1,second: 11) @H_301_32@case .Jack,.Queen,.King: @H_301_32@return Values(first: 10,second: nil) @H_301_32@default: @H_301_32@return Values(first: self.rawValue,second: nil) } } } @H_301_32@let rank: Rank @H_301_32@let suit: Suit @H_301_32@var description: String { @H_301_32@var s = "\(suit.rawValue)" s += "\(rank.values.first)" s += rank.values.second != nil ? " or \(rank.values.second!)" : "" @H_301_32@return s } } @H_301_32@let ace = BlackjackCard(rank: BlackjackCard.Rank.Ace,suit: BlackjackCard.Suit.Diamonds) print(ace) // BlackjackCard(rank: BlackjackCard.Rank.Ace,suit: BlackjackCard.Suit.Diamonds) print(ace.description) // ♢1 or 11
引用嵌套类型
在外部引用嵌套类型时，在嵌套类型的类型名前加上其外部类型的类型名作为前缀。
/** * 一个结构体BlackjackCard（二十一点），用来模拟BlackjackCard中的扑克牌点数。在BlackjackCard中，Ace牌的面值可以是1或者11。 */ @H_301_32@struct BlackjackCard { @H_301_32@enum Suit: Character { @H_301_32@case Spades = "♠" @H_301_32@case Hearts = "♡" @H_301_32@case Diamonds = "♢" @H_301_32@case Clubs = "♣" } @H_301_32@enum Rank: Int { @H_301_32@case Two = 2,second: nil) } } } @H_301_32@let rank: Rank @H_301_32@let suit: Suit @H_301_32@var description: String { @H_301_32@var s = "\(suit.rawValue)" s += "\(rank.values.first)" s += rank.values.second != nil ? " or \(rank.values.second!)" : "" @H_301_32@return s } } @H_301_32@let heartSymbol = BlackjackCard.Suit.Hearts.rawValue print(heartSymbol) // ♡
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题，2h30min8题是比较合理的。
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的相关信息，请在本站寻找。
本文标签：
