本文共 10857 字，大约阅读时间需要 36 分钟。
A.把右上角的凹缺口补上变成凸的就成了规则矩形
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x)#define Sca2(x,y) scanf("%d%d",&x,&y)#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair #define PIL pair #define PLL pair #define pb push_back#define fi first#define se second typedef vector VI;int read(){ int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){ if (c == '-') f = -1;c = getchar();}while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}const double eps = 1e-9;const int maxn = 110;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7; int N,M,K;int main(){ LL w1,h1,w2,h2; scanf("%lld%lld%lld%lld",&w1,&h1,&w2,&h2); LL ans = w1 + w1 + h1 + h1 + h2 + h2 + 4; Prl(ans); return 0;}
B.画在图上就是两条斜线之间有多少可以水平的线，显然是下面这条线的最高点和上面这条线的最低点作差，记得打一个vis标记记录哪些线取过了
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x)#define Sca2(x,y) scanf("%d%d",&x,&y)#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair #define PIL pair #define PLL pair #define pb push_back#define fi first#define se second typedef vector VI;int read(){ int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){ if (c == '-') f = -1;c = getchar();}while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}const double eps = 1e-9;const int maxn = 110;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7; int N,M,K;int main(){ Sca(N); LL la = 0,lb = 0; LL ans = 1; LL now = 1; for(int i = 1; i <= N ; i ++){ LL a,b; scanf("%lld%lld",&a,&b); int t = max(max(la,lb),now); if(min(a,b) >= t){ ans += min(a,b) - t + 1; now = min(a,b) + 1; } la = a; lb = b; } Prl(ans); return 0;}
C.开始觉得要二分，后来觉得要O(n3),仔细一看发现O(n)
显然取两条非递减的线，从最高点往两边降低，贪心的发现每次都升高最高点更低的那个路径就可以了。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x)#define Sca2(x,y) scanf("%d%d",&x,&y)#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair #define PIL pair #define PLL pair #define pb push_back#define fi first#define se second typedef vector VI;int read(){ int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){ if (c == '-') f = -1;c = getchar();}while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}const double eps = 1e-9;const int maxn = 110;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7; int N,M,K;int a[maxn];int b[maxn],c[maxn];int main(){ Sca(N); for(int i = 1; i <= N ; i ++) Sca(a[i]); sort(a + 1,a + 1 + N); int cnt1 = 0,cnt2 = 0; b[++cnt1] = a[1]; c[++cnt2] = a[2]; for(int i = 3; i <= N ; i ++){ if(b[cnt1] < c[cnt2]) b[++cnt1] = a[i]; else c[++cnt2] = a[i]; } for(int i = 1; i <= cnt1; i ++) printf("%d ",b[i]); for(int i = cnt2; i >= 1; i --) printf("%d ",c[i]); return 0;}
D.拓扑排序例题。
先把所有的等于号用并查集合并，找大小之间的冲突。然后用拓扑排序标记顺便判环。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x)#define Sca2(x,y) scanf("%d%d",&x,&y)#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair #define PIL pair #define PLL pair #define pb push_back#define fi first#define se second typedef vector VI;int read(){ int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){ if (c == '-') f = -1;c = getchar();}while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}const double eps = 1e-9;const int maxn = 2010;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7; int N,M,K;char MAP[maxn][maxn];struct Edge{ int to,next;}edge[maxn * maxn * 2];int fa[maxn * 2],tot,head[maxn * 2],ind[maxn * 2];void init(){ for(int i = 0 ; i <= N + M; i ++){ head[i] = -1; fa[i] = i; ind[i] = 0; } tot = 0;}void add(int u,int v){ edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++;}int find(int x){ if(x == fa[x]) return x; return fa[x] = find(fa[x]);}void Union(int a,int b){ a = find(a); b = find(b); fa[a] = b;}int ans[maxn];int main(){ Sca2(N,M); init(); bool flag = 1; for(int i = 1; i <= N ; i ++){ scanf("%s",MAP[i] + 1); for(int j = 1; j <= M ; j ++){ if(MAP[i][j] == '='){ Union(i,j + N); } } } for(int i = 1; i <= N && flag; i ++){ for(int j = 1; j <= M ; j ++){ if(MAP[i][j] == '=') continue; int a = find(i),b = find(j + N); if(a == b){ flag = 0; break; } if(MAP[i][j] == '>'){ add(b,a); ind[a]++; }else{ add(a,b); ind[b]++; } } } if(!flag){ puts("No"); return 0; } queue Q; for(int i = 1; i <= N + M; i ++){ if(find(i) == i && !ind[i]){ ans[i] = 1; Q.push(i); } } while(!Q.empty()){ int u = Q.front(); Q.pop(); for(int i = head[u]; ~i; i = edge[i].next){ int v = edge[i].to; ans[v] = max(ans[v],ans[u] + 1); ind[v]--; if(!ind[v]) Q.push(v); } } for(int i = 1; i <= N + M; i ++){ if(fa[i] == i && ind[i]) flag = 0; } if(!flag){ puts("No"); return 0; } puts("Yes"); for(int i = 1; i <= N ; i ++){ printf("%d ",ans[find(i)]); } puts(""); for(int j = N + 1; j <= N + M; j ++){ printf("%d ",ans[find(j)]); } return 0;}
E.dp[100000][30]记录到i这个字符串j的最长长度。
如果右边的字符串都为k，那么dp[i][j] = max(dp[i][j],len * (dp[i - 1][j] + 1) + dp[i - 1][j]);
否则字符就变为前后缀与他相同的最长长度相加
如果曾经出现过这个字符，这个字符的出现次数至少为1
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x)#define Sca2(x,y) scanf("%d%d",&x,&y)#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair #define PIL pair #define PLL pair #define pb push_back#define fi first#define se second typedef vector VI;int read(){ int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){ if (c == '-') f = -1;c = getchar();}while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}const double eps = 1e-9;const int maxn = 1e5 + 10;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7; int N,M,K;LL ans[40];LL dp[maxn][30];LL pre[100000];LL tmp[30];char str[100000];int main(){ Sca(N); for(int i = 1; i <= N ; i ++){ scanf("%s",str); LL len = strlen(str); LL a = 1,b = len; for(int j = 0 ; j < 26; j ++) tmp[j] = 0; for(int j = 0; j < len; j ++){ if(j && str[j - 1] == str[j]) pre[j] = pre[j - 1] + 1; else pre[j] = 1; tmp[str[j] - 'a'] = max(tmp[str[j] - 'a'],pre[j]); } for(int j = 0 ; j < 26; j ++){ dp[i][j] = tmp[j]; int l = 0,r = len - 1; while(l <= r && str[l] == j + 'a') l++; while(r > l && j + 'a' == str[r]) r--; if(l == len){ dp[i][j] = max(dp[i][j],len * (dp[i - 1][j] + 1) + dp[i - 1][j]); }else if(dp[i - 1][j]){ dp[i][j] = max(dp[i][j],l + len - r); } } } LL sum = 0; for(int j = 0 ; j < 26; j ++) sum = max(sum,dp[N][j]); Prl(sum); return 0;}
F.喜闻乐见的送分F题，开到就是赚到。
并查集模板题，加一个l[maxn],r[maxn]表示这个集合最左最右的数字
nxt[maxn]表示这个数字的下一个数字，每次匹配u,v都把u集合放在v集合的左边，更新一下几个数组
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x)#define Sca2(x,y) scanf("%d%d",&x,&y)#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair #define PIL pair #define PLL pair #define pb push_back#define fi first#define se second typedef vector VI;int read(){ int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){ if (c == '-') f = -1;c = getchar();}while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}const double eps = 1e-9;const int maxn = 150010;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7; int N,M,K;int fa[maxn],r[maxn],l[maxn];int nxt[maxn];void init(){ for(int i = 0 ; i <= N ; i ++){ fa[i] = r[i] = l[i] = i; nxt[i] = -1; } }int find(int x){ if(x == fa[x]) return x; return fa[x] = find(fa[x]);}int main(){ Sca(N); init(); for(int i = 1; i <= N - 1; i ++){ int u,v; Sca2(u,v); u = find(u); v = find(v); nxt[r[u]] = l[v]; l[v] = l[u]; fa[u] = v; } int root = l[find(1)]; for(int i = 1; i <= N ; i ++){ printf("%d ",root); root = nxt[root]; } return 0;}
转载于:https://www.cnblogs.com/Hugh-Locke/p/10725924.html
