Kuma Rider久违的第二场训练，这场很水，又在vj的榜单上看到第一场的大哥了，2小时ak，大哥牛啤！
A.水
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<functional>
#include<vector>
using namespace std;
const double eps = 1e-; int T;
char s[];
int main(void)
{
scanf("%d", &T);
getchar();
while (T--)
{
gets(s);
int len = strlen(s);
int p;
char luo[];
for(int i=;i<=;i++)luo[i]=;
bool fu = false;
int num1 = ;
for (p = ; p < len; p++)
{
//printf("%d %c\n", p, s[p]);
if (s[p] == '-')fu = true;
else if (s[p] >= ''&&s[p] <= '')
{
num1 *= ;
num1 += s[p] - '';
}
else if (s[p] == ' ')continue;
else
{
int tot = ;
while (s[p] != ' ')
{
luo[tot++] = s[p]; p++; }
break;
}
//printf("%d %c\n", p, s[p]);
} if (fu)num1 = -num1;
int num2 = ;
fu = false;
for (p = p + ; p < len; p++)
{
if (s[p] == '-')fu = true;
else if (s[p] >= ''&&s[p] <= '')
{
num2 *= ;
num2 += s[p] - '';
}
}
if (fu)num2 = -num2; if (luo[] == '<')
{
if (luo[] == '=')
{
if (num1 <= num2)printf("true\n");
else printf("false\n");
}
else
{
if (num1 < num2)printf("true\n");
else printf("false\n");
}
}
else if (luo[] == '>')
{
if (luo[] == '=')
{
if (num1 >= num2)printf("true\n");
else printf("false\n");
}
else
{
if (num1 > num2)printf("true\n");
else printf("false\n");
}
}
else if (luo[] == '!')
{
if (num1 != num2)printf("true\n");
else printf("false\n");
}
else
{
if (num1 == num2)printf("true\n");
else printf("false\n");
} } }
B.水
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<functional>
#include<vector>
using namespace std;
const double eps = 1e-; int main(void) {
int t;
scanf("%d", &t);
while (t--) {
int a;
int sum = ;
int fla = ;
for (int i = ; i < ; i++) {
scanf("%d", &a);
if (a <= ) fla = ;
sum += a;
}
if (fla || sum != ) printf("NO\n");
else printf("YES\n");
}
return ;
}
C.背包
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<functional>
#include<vector>
using namespace std;
const double eps = 1e-;
const int inf = 0x3f3f3f3f; int a[];
int dp[];
int sum;
int main(void) {
int t;
scanf("%d", &t);
while (t--)
{
int K, m, n;
sum = ;
scanf("%d%d%d", &n, &m, &K);
for (int i =; i <= K; i++)
{
scanf("%d", &a[i]);
sum += a[i];
}
int sh = n - sum;
if (m <= sh)printf("0\n");
else
{
int need = m - sh;
memset(dp, inf, sizeof(dp));
dp[] = ;
for (int i = ; i <= K; i++)
{
for (int j = sum; j >= a[i]; j--)
{
dp[j] = min(dp[j - a[i]] + , dp[j]);
}
}
int ans = inf;
for (int i = need; i <= sum; i++)
{
ans = min(ans, dp[i]);
}
printf("%d\n", ans); } }
}
D.判断数独对不对（队友没有用函数，暴力得就很真实）
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<functional>
#include<vector>
using namespace std;
const double eps = 1e-;
const int inf = 0x3f3f3f3f;
//
//int a[105];
//int dp[33768];
//int sum;
//int main(void) {
// int t;
// scanf("%d", &t);
// while (t--)
// {
// int K, m, n;
// sum = 0;
// scanf("%d%d%d", &n, &m, &K);
// for (int i =1; i <= K; i++)
// {
// scanf("%d", &a[i]);
// sum += a[i];
// }
// int sh = n - sum;
// if (m <= sh)printf("0\n");
// else
// {
// int need = m - sh;
// memset(dp, inf, sizeof(dp));
// dp[0] = 0;
// for (int i = 1; i <= K; i++)
// {
// for (int j = need; j >= 0; j--)
// {
// dp[j] = min(dp[j - a[i]] + 1, dp[j]);
// }
// }
// printf("%d\n", dp[need]);
//
// }
//
// }
//}
// char ch[][];
int vis[];
int main(void) {
int t;
scanf("%d", &t);
while (t--) {
getchar();
int fla = ;
for (int i = ; i <= ; i++) {
scanf("%s", ch[i]+);
}
for (int i = ; i <= ; i++) {
memset(vis, , sizeof(vis));
int sum = ;
for (int j = ; j <= ; j++) {
if (!vis[ch[i][j] - '']) {
vis[ch[i][j] - ''] = ;
sum++;
}
}
if (sum != ) fla = ;
}
for (int i = ; i <= ; i++) {
memset(vis, , sizeof(vis));
int sum = ;
for (int j = ; j <= ; j++) {
if (!vis[ch[j][i] - '']) {
vis[ch[j][i] - ''] = ;
sum++;
}
}
if (sum != ) fla = ;
}
int sum = ;
memset(vis, , sizeof(vis));
for (int i = ; i <= ; i++) {
for (int j = ; j <= ; j++) {
if (!vis[ch[i][j] - '']) {
vis[ch[i][j] - ''] = ;
sum++;
}
}
}
if (sum != ) fla = ;
sum = ;
memset(vis, , sizeof(vis));
for (int i = ; i <= ; i++) {
for (int j = ; j <= ; j++) {
if (!vis[ch[i][j] - '']) {
vis[ch[i][j] - ''] = ;
sum++;
}
}
}
if (sum != ) fla = ;
sum = ;
memset(vis, , sizeof(vis));
for (int i = ; i <= ; i++) {
for (int j = ; j <= ; j++) {
if (!vis[ch[i][j] - '']) {
vis[ch[i][j] - ''] = ;
sum++;
}
}
}
if (sum != ) fla = ;
sum = ;
memset(vis, , sizeof(vis));
for (int i = ; i <=; i++) {
for (int j = ; j <= ; j++) {
if (!vis[ch[i][j] - '']) {
vis[ch[i][j] - ''] = ;
sum++;
}
}
}
if (sum != ) fla = ;
sum = ;
memset(vis, , sizeof(vis));
for (int i = ; i <= ; i++) {
for (int j = ; j <= ; j++) {
if (!vis[ch[i][j] - '']) {
vis[ch[i][j] - ''] = ;
sum++;
}
}
}
if (sum != ) fla = ;
sum = ;
memset(vis, , sizeof(vis));
for (int i = ; i <= ; i++) {
for (int j = ; j <= ; j++) {
if (!vis[ch[i][j] - '']) {
vis[ch[i][j] - ''] = ;
sum++;
}
}
}
if (sum != ) fla = ;
sum = ;
memset(vis, , sizeof(vis));
for (int i = ; i <= ; i++) {
for (int j = ; j <= ; j++) {
if (!vis[ch[i][j] - '']) {
vis[ch[i][j] - ''] = ;
sum++;
}
}
}
if (sum != ) fla = ;
sum = ;
memset(vis, , sizeof(vis));
for (int i = ; i <= ; i++) {
for (int j = ; j <= ; j++) {
if (!vis[ch[i][j] - '']) {
vis[ch[i][j] - ''] = ;
sum++;
}
}
}
if (sum != ) fla = ;
sum = ;
memset(vis, , sizeof(vis));
for (int i = ; i <= ; i++) {
for (int j = ; j <= ; j++) {
if (!vis[ch[i][j] - '']) {
vis[ch[i][j] - ''] = ;
sum++;
}
}
}
if (sum != ) fla = ;
if (fla) printf("Invalid\n");
else {
printf("Valid\n");
}
}
}
E.树状数组
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<functional>
#include<vector>
using namespace std; const int maxn = ;
int c[maxn], a[maxn];
int n;
int lowbit(int x) {
return x&(-x);
}
void update_onepos(int pos, int x) {
while (pos <= n) {
c[pos] += x;
pos += lowbit(pos);
}
}
int getsum_onepos(int pos) {
int sum = ;
while (pos > ) {
sum += c[pos];
pos -= lowbit(pos);
}
return sum;
}
int getsum_range(int x1, int x2) {
return getsum_onepos(x2) - getsum_onepos(x1-);
}
int ax[];
int main(void) {
int t;
scanf("%d", &t);
while (t--) {
int nn;
n = -;
scanf("%d", &nn);
memset(c, , sizeof(c));
for (int i = ; i < nn; i++) {
scanf("%d", &ax[i]);
n = max(ax[i], n);
}
n += ;
for (int i = ; i < nn; i++) {
update_onepos(ax[i], );
}
int sum = ;
for (int i = ; i < nn; i++) {
sum += getsum_range(max(, ax[i] - ), ax[i])-;
sum += getsum_range(ax[i] + , ax[i] + );
}
printf("%d\n", sum / );
}
return ;
}
F.并查集，最后统计根节点的问号数量
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<functional>
#include<vector>
using namespace std;
typedef long long LL;
const int maxv = ;
const LL mod = 1e9 + ; int T, n, m;
char s[maxv];
bool hav ;
struct Node
{
int pos;
int fa;
char ch;
}tree[]; int find(int nx)
{
if (tree[nx].fa == nx)return nx; int ff = find(tree[nx].fa);
tree[nx].ch = tree[ff].ch;
return tree[nx].fa=ff;
} bool vis[]; void init()
{
hav = false;
scanf("%d %d", &n, &m);
scanf("%s", s + );
for (int i = ; i <= n; i++)
{
if (s[i] == '?')hav = true;
tree[i].fa = i;
tree[i].ch = s[i];
tree[i].pos = i;
vis[i] = false;
}
} int main(void)
{
scanf("%d", &T);
while (T--)
{
init();
bool can = true; for (int i = ; i <= m; i++)
{
int u, v;
scanf("%d %d", &u, &v);
int fx = find(u), fy = find(v);
if (fx != fy)
{
//printf("%d %d\n", fx, fy);
if (tree[fx].ch!='?'&&tree[fy].ch!='?')
{
if (tree[fx].ch != tree[fy].ch)can = false;
}
else if (tree[fx].ch == '?'&&tree[fy].ch != '?')
{
tree[fx].fa = fy;
tree[fx].ch = tree[fy].ch;
}
else if (tree[fx].ch != '?'&&tree[fy].ch == '?')
{
tree[fy].fa = fx;
tree[fy].ch = tree[fx].ch;
}
else
{
tree[fx].fa = fy;
tree[fx].ch = tree[fy].ch;
}
}
} int l = , r = n;
while (l <= r)
{
int fx = find(l), fy = find(r);
if (fx != fy)
{
//printf("%d %d\n", fx, fy);
if (tree[fx].ch != '?'&&tree[fy].ch != '?')
{
if (tree[fx].ch != tree[fy].ch)can = false;
}
else if (tree[fx].ch == '?'&&tree[fy].ch != '?')
{
tree[fx].fa = fy;
tree[fx].ch = tree[fy].ch;
}
else if (tree[fx].ch != '?'&&tree[fy].ch == '?')
{
tree[fy].fa = fx;
tree[fy].ch = tree[fx].ch;
}
else
{
tree[fx].fa = fy;
tree[fx].ch = tree[fy].ch;
}
}
l++, r--;
} if (!can){printf("0\n"); continue;} for (int i = ; i <= n; i++)
{
int fx = find(i);
s[i] = tree[fx].ch;
} //printf("%s\n", s + 1); LL ans = ;
bool tag = true; for (int i = ; i <= n; i++)
{
int fx = find(i);
if (!vis[fx])
{
if (tree[fx].ch == '?')
{
ans *= ;
ans %= mod;
}
vis[fx] = true;
}
} if (tag)
{
if (hav&&ans == )printf("1\n");
else if(!hav)printf("0\n");
else printf("%lld\n", ans);
}
else printf("0\n"); }
return ;
}
G.状压dp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<functional>
#include<vector>
using namespace std;
const int maxv = ; int T, n, m;
string s;
map<string, int>mp;
int in[maxv], w[maxv];
int dp[ << ]; int main()
{
cin >> T;
while (T--)
{
cin >> n >> m;
memset(dp, -, sizeof(dp));
getchar();
for (int i = ; i <= n; i++)
{
in[i] = ;
w[i] = ;
}
mp.clear();
for (int i = ; i < n; i++)
{
getline(cin, s);
int pos = -;
for (int j = ; j < s.size(); j++)
{
if (s[j] <= ''&&s[j] >= '')
{
pos = j;
break;
}
}
string tmp = s.substr(, pos - );
int ww = ;
string shuzi = s.substr(pos, s.size() - pos);
for (int j = ; j < shuzi.size(); j++)
{
ww = ww * + shuzi[j] - '';
}
mp[tmp] = i;
w[i] = ww;
//cout << tmp << " " << ww << endl;
}
for (int i = ; i <= m; i++)
{
getline(cin, s);
int pos1 = -;
for (int i = ; i < s.size(); i++)
{
if (s[i] == '-')
{
pos1 = i;
break;
}
}
string t1 = s.substr(, pos1 - );
string t2 = s.substr(pos1 + , s.size() - pos1 - );
int id1 = mp[t1];
int id2 = mp[t2];
in[id2] |= ( << id1);
}
dp[] = ;
for (int j = ; j < ( << n) - ; j++)
{
if (dp[j] < )
{
continue;
}
int num = ;
for (int i = ; i < n; i++)
{
num += (j >> i & );
}
for (int i = ; i < n; i++)
{
int now = j | ( << i);
if (j != now && (in[i] & j) == in[i])
{
dp[now] = max(dp[now], dp[j] + (num + )*w[i]);
}
}
}
cout << dp[( << n) - ] << endl;
}
return ;
} /*
1
3 2
Implementation 3
Dynamic Programming 10
Greedy 7
Greedy --> Dynamic Programming
Implementation --> Dynamic Programming
*/
H.模板题，待施工
gym100676 [小熊骑士限定]2015 ACM Arabella Collegiate Programming Contest的更多相关文章
-
边双连通缩点+树dp 2015 ACM Arabella Collegiate Programming Contest的Gym - 100676H
http://codeforces.com/gym/100676/attachments 题目大意: 有n个城市,有m条路,每条路都有边长,如果某几个城市的路能组成一个环,那么在环中的这些城市就有传送 ...
-
Codeforces Gym 2015 ACM Arabella Collegiate Programming Contest（二月十日训练赛）
A(By talker): 题意分析:以a(int) op b(int)形式给出两个整数和操作符, 求两个整数是否存在操作符所给定的关系 ,有则输出true,无则输出false: 思路:由于无时间复杂 ...
-
2015 ACM Arabella Collegiate Programming Contest
题目链接:https://vjudge.net/contest/154238#overview. ABCDE都是水题. F题,一开始分类讨论,结果似乎写挫了,WA了一发.果断换并查集上,A了. G题, ...
-
18春季训练01-3/11 2015 ACM Amman Collegiate Programming Contest
Solved A Gym 100712A Who Is The Winner Solved B Gym 100712B Rock-Paper-Scissors Solved C Gym 100712C ...
-
ACM Arabella Collegiate Programming Contest 2015 F. Palindrome 并查集
题目链接:http://codeforces.com/gym/100676/attachments 题意: 给一个字符串,有一些约束条件,两个位置要相同,有一些是问号,求最后有多少种方案回文? 分析: ...
-
ACM Arabella Collegiate Programming Contest 2015 H. Capital City 边连通分量
题目链接:http://codeforces.com/gym/100676/attachments 题意: 有 n 个点,m 条边,图中,边强连通分量之间可以直达,即距离为 0 ,找一个点当做首都,其 ...
-
2017 ACM Arabella Collegiate Programming Contest(solved 11/13)
省选考前单挑做点ACM练练细节还是很不错的嘛- 福利:http://codeforces.com/gym/101350 先来放上惨不忍睹的virtual participate成绩(中间跑去食堂吃饭于 ...
-
带权并查集：CF-2015 ACM Arabella Collegiate Programming Contest（F题）
F. Palindrome Problem Description A string is palindrome if it can be read the same way in either di ...
-
2015 ACM Syrian Collegiate Programming Contest
A. My Friend of Misery 计算出答案的上下界即可. 时间复杂度$O(n)$. #include<bits/stdc++.h> using namespace std; ...
随机推荐
-
让UITableView 的 headerView跟随 cell一起滚动,tableHeaderView
在进行UITableView开发的时候,我们有时希望在cell的上面放置一些按钮之类的空间,又想让这些空间跟着cell一起滚动,刚开始想着hederView,注意,这是tableView的sectio ...
-
PHP获取中文汉字首字母方法
function getFirstLetter($str){ $fchar = ord($str{0}); if($fchar >= ord("A") and $fchar ...
-
iOS 自定义layer的两种方式
在iOS中,你能看得见摸得着的东西基本都是UIView,比如一个按钮,一个标签,一个文本输入框,这些都是UIView: 其实UIView之所以能显示在屏幕上,完全是因为它内部的一个图层 在创建UIVi ...
-
RedHat6.2 x86手动配置LNMP环境
因为公司要求用RedHat配,顺便让我练习一下Linux里面的操作什么的. 折腾来折腾去终于搞好了,其实也没那么难嘛.但是也要记录一下. 首先,是在服务器里面用VMware搭建的RedHat6.2 x ...
-
Spring 数据库读写分离
读写分离常见有俩种方式 1 第一种方式比较常用就是定义2个数据库连接,一个是Master,另一个是Slave.更新数据时我们取Master,查询数据时取Slave.太过简单不做介绍. 2 第二种方数据 ...
-
Oracle调整顾问(SQL Tuning Advisor 与 SQL Access Advisor
在Oracle数据库出现性能问题时,使用Oracle本身的工具包,给出合理的调优建议是比较省力的做法. tuning advisor 是对输入的sql set的执行计划进行优化accsee advis ...
-
If you want an embedded database (H2, HSQL or Derby), please put it on the classpath.
学习Spring Boot 过程中遇到了下列这个问题 Description: Failed to configure a DataSource: 'url' attribute is not spe ...
-
laravel orm进行增删改查
https://laravelacademy.org/post/9699.html 建议用DB门面直接操作数据库,因为ORM性能低.数据查询上面,ORM不会比DB差的,就比如with,是用了sql最基 ...
-
使用ApiPost模拟发送get、post、delete、put等http请求
现在的模拟发送请求插件很多比如老外的postman等,但亲测咱们国内的 ApiPost 更好用一些,因为它不仅可以模拟发送get.post.delete.put请求,还可以导出文档,支持团队协作也是它 ...
-
为autoLayout 增加标识符，方便调试
 如上图,是一个十分简单的布局. root view 上加了一个 button 和一个 webview. 不加标识符的样子 视图层级中没有标识  只有 UIView.WKWebView 之类,如果 ...