A Palindromic Twist(字符串)

　　问每个字母必须向左或向右变成另一个字母，问能不能构成回文

 #include <iostream>

 #include <string.h>

 #include <cstdio>

 #include <vector>

 #include <stack>

 #include <math.h>

 #include <string>

 #include <algorithm>

 #include <time.h>

 #define SIGMA_SIZE 26

 #define lson rt<<1

 #define rson rt<<1|1

 #define lowbit(x) (x&-x)

 #define foe(i, a, b) for(int i=a; i<=b; i++)

 #define fo(i, a, b) for(int i=a; i<b; i++);

 //#pragma warning ( disable : 4996 )

 using namespace std;

 typedef long long LL;

 inline LL LMax(LL a, LL b) { return a>b ? a : b; }

 inline LL LMin(LL a, LL b) { return a>b ? b : a; }

 inline LL lgcd(LL a, LL b) { return b ==  ? a : lgcd(b, a%b); }

 inline LL llcm(LL a, LL b) { return a / lgcd(a, b)*b; }  //a*b = gcd*lcm

 inline int Max(int a, int b) { return a>b ? a : b; }

 inline int Min(int a, int b) { return a>b ? b : a; }

 inline int gcd(int a, int b) { return b ==  ? a : gcd(b, a%b); }

 inline int lcm(int a, int b) { return a / gcd(a, b)*b; }  //a*b = gcd*lcm

 const LL INF = 0x3f3f3f3f3f3f3f3f;

 const LL mod = ;

 const double eps = 1e-;

 const int inf = 0x3f3f3f3f;

 const int maxk = 1e6 + ;

 const int maxn = 5e5+;

 int len;

 char str[];

 int main()

 {

     #ifndef ONLINE_JUDGE

         freopen("input.txt", "r", stdin);

     #endif

     int T; cin >> T;

     while(T--)

     {

         scanf("%d", &len);

         scanf("%s", str+);

         if (len == )

         {

             printf("YES");

             continue;

         }

         int mid;

         int l, r, tmp;

         bool ok = true;

         mid = len/;

         for ( int i = ; i <= mid; i++ )

         {

             l = i; r = len-i+;

             tmp = abs(str[l]-str[r]);

             if (tmp >  || tmp == )

             {

                 //cout << tmp << endl;

                 ok = false;

                 break;

             }

         }

         if (ok)

             printf("YES\n");

         else

             printf("NO\n");

     }

     return ;

 }

　　

　　B Numbers on the Chessboard(模拟)

　　题意简单，写起来容易错，主要是将矩阵每两层作为一大层(+N)，然后判断所在点是前面有几层

 #include <iostream>

 #include <string.h>

 #include <cstdio>

 #include <vector>

 #include <stack>

 #include <math.h>

 #include <string>

 #include <algorithm>

 #include <time.h>

 #define SIGMA_SIZE 26

 #define lson rt<<1

 #define rson rt<<1|1

 #define lowbit(x) (x&-x)

 #define foe(i, a, b) for(int i=a; i<=b; i++)

 #define fo(i, a, b) for(int i=a; i<b; i++);

 //#pragma warning ( disable : 4996 )

 using namespace std;

 typedef long long LL;

 inline LL LMax(LL a, LL b) { return a>b ? a : b; }

 inline LL LMin(LL a, LL b) { return a>b ? b : a; }

 inline LL lgcd(LL a, LL b) { return b ==  ? a : lgcd(b, a%b); }

 inline LL llcm(LL a, LL b) { return a / lgcd(a, b)*b; }  //a*b = gcd*lcm

 inline int Max(int a, int b) { return a>b ? a : b; }

 inline int Min(int a, int b) { return a>b ? b : a; }

 inline int gcd(int a, int b) { return b ==  ? a : gcd(b, a%b); }

 inline int lcm(int a, int b) { return a / gcd(a, b)*b; }  //a*b = gcd*lcm

 const LL INF = 0x3f3f3f3f3f3f3f3f;

 const LL mod = ;

 const double eps = 1e-;

 const int inf = 0x3f3f3f3f;

 const int maxk = 1e6 + ;

 const int maxn = 5e5+;

 LL n, q;

 int main()

 {

     #ifndef ONLINE_JUDGE

         freopen("input.txt", "r", stdin);

     #endif

     cin >> n >> q;

     int x, y;

     while(q--)

     {

         LL ans = ;

         LL tmp;

         scanf("%d %d", &x, &y);

         if ((x+y)%==) {

             int h = x%;

             tmp = h ? x/ : (x-)/;

             if (h) {

                 ans = n*tmp + (y/)+;

             }

             else {

                 ans = n*tmp + (n/)+(y/);

                 if (n%) ans++;

             }

         }

         else {

             int h = x%;

             tmp = h ? x/ : (x-)/;

             if (h) {

                 ans = n*tmp + (y/);

             }

             else {

                 ans = n*tmp + (n/) + (y+)/;

             }

             if (n%)

                 ans += (n*n)/+;

             else

                 ans += (n*n)/;

         }

         printf("%lld\n", ans);

     }

     return ;

 }

　　

　　C Minimum Value Rectangle　

　　很容易推出最后结果和(a/b)+(b/a)有关，根据均值不等式肯定两个值越近越小，所以把可行边排序后每次选择枚举距离最相近的两种边选最小

 #include <iostream>

 #include <string.h>

 #include <cstdio>

 #include <vector>

 #include <stack>

 #include <math.h>

 #include <string>

 #include <algorithm>

 #include <time.h>

 #define SIGMA_SIZE 26

 #define lson rt<<1

 #define rson rt<<1|1

 #define lowbit(x) (x&-x)

 #define foe(i, a, b) for(int i=a; i<=b; i++)

 #define fo(i, a, b) for(int i=a; i<b; i++)

 //#pragma warning ( disable : 4996 )

 using namespace std;

 typedef long long LL;

 inline LL LMax(LL a, LL b) { return a>b ? a : b; }

 inline LL LMin(LL a, LL b) { return a>b ? b : a; }

 inline LL lgcd(LL a, LL b) { return b ==  ? a : lgcd(b, a%b); }

 inline LL llcm(LL a, LL b) { return a / lgcd(a, b)*b; }  //a*b = gcd*lcm

 inline int Max(int a, int b) { return a>b ? a : b; }

 inline int Min(int a, int b) { return a>b ? b : a; }

 inline int gcd(int a, int b) { return b ==  ? a : gcd(b, a%b); }

 inline int lcm(int a, int b) { return a / gcd(a, b)*b; }  //a*b = gcd*lcm

 const LL INF = 0x3f3f3f3f3f3f3f3f;

 const LL mod = ;

 const double eps = 1e-;

 const int inf = 0x3f3f3f3f;

 const int maxk = 1e6+;

 const int maxn = 1e6+;

 int n, cnt;

 int a[maxn];

 int num[maxn];

 void init()

 {

     cin >> n;

     cnt = ;

     int tmp;

     foe(i, , n)

         scanf("%d", &a[i]);

     sort(a+, a++n);

     tmp = ;

     foe(i, , n)

     {

         if (a[i] == a[i-]) {

             if (!tmp) {

                 num[++cnt] = a[i];

                 tmp++;

             }

             else {

                 tmp = ;

             }

         }

         else {

             tmp = ;

         }

     }

 }

 int main()

 {

     #ifndef ONLINE_JUDGE

         freopen("input_2.txt", "r", stdin);

     #endif

     int T; cin >> T;

     while(T--)

     {

         init();

         double tmp, ans = inf;

         int a, b;

         //cout << cnt << endl;

         fo(i, , cnt)

         {

             tmp = (double)*num[i]/num[i+] + (double)*num[i+]/num[i];

             if ( tmp < ans )

             {

                 ans = tmp;

                 a = i; b = i+;

             }

         }

         printf("%d %d %d %d\n", num[a], num[a], num[b], num[b]);

     }

     return ;

 }

　　

　　D Mouse Hunt

　　有只耗子在n个房子内乱串，当此时刻耗子在i房间时，下一时刻耗子会移动到a[i]号房间，在i房间布置捕鼠器需要耗费c[i]，开始耗子位置随机，问最少消耗多少能保证一定捕捉到老鼠

　　根据题意我们需要判断连通量和环，因为耗子顺着一条路走下去最后必然在某一个点后走到原先的某点形成一个环，所以用并查集判环，在该环上寻找最小cost就行了

 #include <iostream>

 #include <string.h>

 #include <cstdio>

 #include <vector>

 #include <stack>

 #include <math.h>

 #include <string>

 #include <algorithm>

 #include <time.h>

 #define SIGMA_SIZE 26

 #define lson rt<<1

 #define rson rt<<1|1

 #define lowbit(x) (x&-x)

 #define foe(i, a, b) for(int i=a; i<=b; i++)

 #define fo(i, a, b) for(int i=a; i<b; i++)

 //#pragma warning ( disable : 4996 )

 using namespace std;

 typedef long long LL;

 inline LL LMax(LL a, LL b) { return a>b ? a : b; }

 inline LL LMin(LL a, LL b) { return a>b ? b : a; }

 inline LL lgcd(LL a, LL b) { return b ==  ? a : lgcd(b, a%b); }

 inline LL llcm(LL a, LL b) { return a / lgcd(a, b)*b; }  //a*b = gcd*lcm

 inline int Max(int a, int b) { return a>b ? a : b; }

 inline int Min(int a, int b) { return a>b ? b : a; }

 inline int gcd(int a, int b) { return b ==  ? a : gcd(b, a%b); }

 inline int lcm(int a, int b) { return a / gcd(a, b)*b; }  //a*b = gcd*lcm

 const LL INF = 0x3f3f3f3f3f3f3f3f;

 const LL mod = ;

 const double eps = 1e-;

 const int inf = 0x3f3f3f3f;

 const int maxk = 1e6+;

 const int maxn = 2e5+;

 int n;

 int cost[maxn], to[maxn];

 int fa[maxn];

 bool vis[maxn];

 vector<int> ans;

 int _find(int x)

 {

     if (x == fa[x])

         return fa[x];

     return fa[x] = _find(fa[x]);

 }

 //将y作为父节点

 void merge(int x, int y)

 {

     int xr = _find(x);

     int yr = _find(y);

     if (xr != yr)

         fa[xr] = y;

 }

 int dfs(int x, int y)

 {

     if (x == y) return cost[x];

     return Min(dfs(x, to[y]), cost[y]);

 }

 void init()

 {

     cin >> n;

     foe(i, , n) scanf("%d", &cost[i]);

     foe(i, , n)

     {

         scanf("%d", &to[i]);

         fa[i] = i;

         vis[i] = false;

     }

 }

 int main()

 {

     #ifndef ONLINE_JUDGE

         freopen("input.txt", "r", stdin);

     #endif

     init();

     //并查集判环

     foe(i, , n) {

         if (_find(to[i]) == _find(i)) {

             vis[i] = true;

             continue;

         }

         merge(i, to[i]);

     }

     int ans = ;

     //foe(i, 1, n)

     //    printf("%d\n", vis[i]);

     foe(i, , n)

         if (vis[i])

            ans += dfs(i, to[i]);

     printf("%d\n", ans);

     return ;

 }

最新文章

  1. Python全栈【异常处理】
  2. 光标失去焦点事件 onblur
  3. sql复习第四次
  4. 【Java每日一题】20161215
  5. Swift中文基础教程----下标
  6. WeedFS0.6.8-引用库列表
  7. php实现发送邮件
  8. 防止ViewPager中的Fragment被销毁的方法，更加流畅
  9. [BZOJ1951][SDOI2005]古代猪文（数论好题）
  10. php计算脚本执行时间
  11. SQL Server系统表sysobjects介绍与使用(转)
  12. 原生Javascript实现图片轮播效果
  13. Complete Guide for Spring Boot Actuator
  14. NYOJ202 红黑树 【预购】
  15. Linux教学辅助训练（第二阶段）
  16. Spring OAuth2 GitHub 自定义登录信息
  17. 与班尼特&#183;胡迪一起找简单规律（HZOJ-2262）
  18. redis远程连接报错记录
  19. 截取 还没有读的txt章节 生成新的文件
  20. Modbus库开发笔记：Modbus ASCII Master开发

热门文章

  1. BZOJ 2159: Crash 的文明世界(组合数学+第二类斯特林数+树形dp)
  2. csp-s模拟测试91
  3. LeetCode刷题笔记-贪心法-格雷编码
  4. JAVA泛型知识（一）
  5. 什么是css块级元素和内联元素
  6. sql实现查询某个字段在哪个表里 及结构是什么
  7. HDU 3966 /// 树链剖分+树状数组
  8. css3的选择器
  9. Spark RDD API（scala）
  10. YARN框架与MapReduce1.0框架的对比分析