A Accurately Say "CocaCola"!
暴力 求出 符合条件的情况好了， 反正一定是止于700的
#include<cstdio>
#include<cstring>
bool check(int x)
{
do
if(x % 10 ==7) return 1;
while(x /= 10);
return 0;
}
int main(void)
{
int T, n, ans = -1, tem;
scanf("%d", &T);
while(T--)
{
scanf("%d",&n);
tem = 0; ans = -1;
for(int i = 1; i < 700; ++i)
if(i % 7 ==0 || check(i))
{
++tem;
if(tem >=n)
{
ans = i - tem + 1;
break;
}
}
else tem = 0;
if(ans == -1) ans = 700;
printf("%d\n", ans);
}
return 0;
}
b Build The Electric System
普里姆算法模板
#include <vector>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
const int LMT = 502;
vector<int> gra[LMT];
int len[LMT][LMT];
bool vis[LMT];
struct mydis
{
int node, len;
bool operator > (const mydis & y)const
{
return len > y.len;
}
mydis(int a, int b): node(a), len(b){}
};
struct cmp
{
bool operator ()(mydis a, mydis b)
{
return a > b;
}
};
priority_queue<mydis, vector<mydis>, cmp> que;
void init(void)
{
int i = 0;
for(i = 0; i < LMT; ++i)gra[i].clear();
while(!que.empty()) que.pop();
memset(vis, 0, sizeof(vis));
}
int main(void)
{
int i, j, T, n, m, from, to, ans;
scanf("%d", &T);
while(T--)
{
init();
scanf("%d%d", &n, &m);
while(m--)
{
scanf("%d%d", &from, &to);
scanf("%d", &len[from][to]);
len[to][from] = len[from][to];
gra[from].push_back(to);
gra[to].push_back(from);
}
que.push(mydis(0, 0));
ans = 0;
for(i = 0; i < n && !que.empty();)
{
from = que.top().node;
if(vis[from])
{
que.pop();
continue;
}
vis[from] = 1;
ans += que.top().len;
que.pop();
for(j = 0; j < gra[from].size(); ++j)
{
to = gra[from][j];
if(0 == vis[to]) que.push(mydis(to, len[from][to]));
}
++i;
}
printf("%d\n", ans);
}
return 0;
}
C Colorful Rainbows
假设几何中的直线为 y = ai x + bi;
假设在区间（down,up）中 y = aix + bi > any y = aj x + bj i !=j
可以两两枚举直线，算出每个直线是否存在这样的down up
#include <cstdio>
#include <cstring>
#define inf 1e30
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
const int LMT = 5002;
double up_lim[LMT], dn_lim[LMT], a[LMT], b[LMT];
void init(void)
{
for(int i = 0; i < LMT; ++i)
{
up_lim[i] = inf;
dn_lim[i] = -inf;
}
}
int main(void)
{
int T, n, i, j, ans;
double pos;
scanf("%d", &T);
while(T--)
{
init();
ans = 0;
scanf("%d", &n);
for(i = 0; i < n; ++i)
scanf("%lf%lf", &a[i], &b[i]);
for(i = 0; i < n; ++i)
for(j = i + 1; j < n; ++j)
{
pos = (b[j] - b[i])/(a[i] - a[j]);
if(a[i] - a[j] > 0)
{
dn_lim[i] = max(dn_lim[i], pos);
up_lim[j] = min(up_lim[j], pos);
}
else if(a[i] - a[j] < 0)
{
dn_lim[j] = max(dn_lim[j], pos);
up_lim[i] = min(up_lim[i], pos);
}
else
{
if(b[i] > b[j])
{
dn_lim[j] = inf;
up_lim[j] = -inf;
}
else
{
dn_lim[i] = inf;
up_lim[i] = -inf;
}
}
}
for(i = 0; i < n; ++i)
if(dn_lim[i] < up_lim[i]) ++ans;
printf("%d\n", ans);
}
return 0;
}
D 贪心+二分， 神题不会啊．．
E 水
F 水
G give me the number
STL 运用题，一开始居然会忘记写‘ten’的值， 残了..
#pragma warning(disable:4786)
#include <cstdio>
#include <map>
#include <string>
#include <set>
#include <cstring>
using namespace std;
const int LMT = 20;
map<string, int> mp;
set<string> rank;
int main(void)
{
int T, ans, num,tem;
char sec[12];
char tag;
mp["zero"] = 0; mp["one"] = 1; mp["two"] = 2; mp["three"] = 3;
mp["four"] = 4; mp["five"] = 5; mp["six"] = 6; mp["seven"] = 7;
mp["eight"] = 8; mp["nine"] = 9; mp["eleven"] = 11; mp["twelve"] = 12;
mp["ten"] = 10;
mp["thirteen"] = 13; mp["fourteen"] = 14; mp["fifteen"] = 15;
mp["sixteen"] = 16; mp["seventeen"] = 17; mp["eighteen"] = 18;
mp["nineteen"] = 19; mp["twenty"] = 20; mp[ "thirty"] = 30;
mp["forty"] = 40; mp["fifty"] = 50;
mp["sixty"] = 60; mp["seventy"] = 70; mp["eighty"] = 80;
mp["ninety"] = 90; mp["thousand"] = 1000; rank.insert("thousand");
mp["million"] = 1000000; rank.insert("million");
mp["hundred"] = 100;
scanf("%d", &T);
while(T--)
{
ans = 0;
tem = 0;
while(~scanf("%s", sec))
{
if(rank.find(sec) != rank.end())
{
num = mp[sec];
ans += tem * num;
tem = 0;
}
else if(strcmp(sec,"hundred") == 0)
tem *= 100;
else
tem += mp[sec];
tag = getchar();
if(tag == '\n') break;
}
ans += tem;
printf("%d\n", ans);
}
return 0;
}
H hurdles of 110m
简单DP ，补充体力那个状态要小心
#include<cstdio>
#include<cstring>
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
const int LMT = 112;
const int inf = 1e9;
int dp[LMT][LMT],cos[3],t[3];
void init()
{
for(int i = 0; i < LMT; ++i)
for(int j = 0; j < LMT; ++j)
dp[i][j] = inf;
}
int main(void)
{
int T, n, m, i, j, sta, ans;
scanf("%d", &T);
while(T--)
{
init();
ans = inf;
scanf("%d%d", &n, &m);
dp[0][m] = 0;
for(i = 1; i <= n; ++i)
{
scanf("%d%d%d%d%d", &t[0], &t[1], &t[2], &cos[0], &cos[2]);
cos[0] *= -1;
for(sta = 0; sta < 3; ++sta)
for(j = m; j >=max(0, cos[sta]); --j)
if(dp[i - 1][j - cos[sta]] < inf && j - cos[sta] <= m)
dp[i][j] = min(dp[i][j], dp[i - 1][j - cos[sta]] + t[sta]);
for(j = m; j > m - cos[2] && j >= 0; --j)
if(dp[i - 1][j] < inf)
dp[i][m] = min(dp[i][m], dp[i - 1][j] + t[2]);
}
for(i = 0; i <= m; ++i)
ans = min(ans, dp[n][i]);
printf("%d\n", ans);
}
return 0;
}
I 巨烦， 靠even神了
G just pour the water
矩阵乘法 被K = 0的情况坑了
#include <cstdio>
#include <cstring>
const int LMT = 22;
struct matrix
{
int n, m;
double mat[LMT][LMT];
matrix (int a, int b): n(a), m(b)
{
memset(mat, 0, sizeof(mat));
}
void clear(void)
{
memset(mat, 0, sizeof(mat));
}
void get_e(void)
{
clear();
for(int i = 0; i < n; ++i)
mat[i][i] = 1.0;
}
};
matrix operator * (const matrix &a, const matrix &b)
{
matrix res(a.n, b.m);
for(int k = 0; k < a.m; ++k)
for(int i =0; i < a.n; ++i)
for(int j = 0; j < b.m; ++j)
res.mat[i][j] += a.mat[i][k] * b.mat[k][j];
return res;
}
matrix mypow(matrix para, int p)
{
matrix res(para.n, para.m);
res.get_e();
while(p)
{
if(p & 1) res = res * para;
p >>= 1;
para = para * para;
}
return res;
}
int main(void)
{
int T, i, j, to;
scanf("%d", &T);
while(T--)
{
int n, k,m;
scanf("%d", &n);
matrix ori(n, 1), work(n, n);
for(i = 0; i < n; ++i)
scanf("%lf", &ori.mat[i][0]);
for(i = 0; i < n; ++i)
{
scanf("%d", &k);
for(j = 0; j < k; ++j)
{
scanf("%d", &to);
--to;
work.mat[to][i] += 1.0/k;
}
if(0 == k) work.mat[i][i] = 1;
}
scanf("%d", &m);
work = mypow(work, m);
ori = work * ori;
for(i = 0; i < n; ++i)
{
if(i)printf(" ");
printf("%.2lf", ori.mat[i][0]);
}
printf("\n");
}
return 0;
}
K king of fuwas
难道不该用%I64d输出的时候用，会判PE？？？
#include <cstdio>
#include <cstring>
const int LMT = 255;
typedef int LL;
char gra[LMT][LMT];
int have[5][LMT][LMT];
int is[100];
LL ans;
int main(void)
{
int T, n, m, i, j, ii;
scanf("%d", &T);
is['B'] = 0; is['H'] = 2;
is['J'] = 1; is['Y'] = 3;
is['N'] = 4;
while(T--)
{
memset(have, 0 , sizeof(have));
ans = 0;
scanf("%d%d", &n, &m);
for(i = 0; i < n; ++i)
scanf("%s", gra[i]);
for(j = 0; j < m; ++j)
for(i = 0; i < n; ++i)
for(ii = i + 1; ii < n; ++ii)
if(gra[i][j] == gra[ii][j])
++have[is[gra[i][j]]][i][ii];
for(i = 0; i < n; ++i)
for(ii = i + 1; ii < n; ++ii)
{
ans += LL(1) * have[0][i][ii] * (have[0][i][ii] - 1)/2;
ans += LL(1) * have[1][i][ii] * (have[1][i][ii] - 1)/2;
ans += LL(1) * have[2][i][ii] * (have[2][i][ii] - 1)/2;
ans += LL(1) * have[3][i][ii] * (have[3][i][ii] - 1)/2;
ans += LL(1) * have[4][i][ii] * (have[4][i][ii] - 1)/2;
}
printf("%d\n", ans);
}
return 0;
}
L 水，一年前搞过了...