1.C 循环

线性同余方程

#include 
#include using namespace std;typedef long long LL;LL exgcd(LL a, LL b, LL &x, LL &y) {if (b == 0) {x = 1, y = 0;return a;}LL d = exgcd(b, a % b, y, x);y -= a / b * x;return d;
}int main() {LL a, b, c, k;while (scanf("%lld%lld%lld%lld", &a, &b, &c, &k), a || b || c || k) {LL x, y, z = 1ll << k;LL d = exgcd(c, z, x, y);if ((b - a) % d)  printf("FOREVER\n");else {x *= (b - a) / d;z /= d;printf("%lld\n", (x % z + z) % z);}}return 0;
}

2.正则问题

理解了这个正则表达式的含义以后，就可以做了，类似于简单的表达式求值的算法，递归和栈都可以

#include 
#include using namespace std;int k;
string s;int dfs() {int res = 0;while (k < s.size()) {if (s[k] == '(') {k ++;res += dfs();k ++;}else if (s[k] == '|') {k ++;res = max(res, dfs());}else if (s[k] == ')') break;else {k ++;res ++;}}return res;
}int main() {cin >> s;return cout << dfs() << endl, 0;
}

3.糖果

IDA*+剪枝(每次选分值最少+去重)

#include 
#include 
#include 
#include using namespace std;const int N = 110, M = 1 << 20;int n, m, k;
vector col[N];
int log2[M];int lowbit(int x)
{return x & -x;
}int h(int state)  // 最少需要再选几行
{int res = 0;for (int i = (1 << m) - 1 - state; i; i -= lowbit(i)){int c = log2[lowbit(i)];res ++ ;for (auto row : col[c]) i &= ~row;}return res;
}bool dfs(int depth, int state)
{if (!depth || h(state) > depth) return state == (1 << m) - 1;// 找到选择性最少的一列int t = -1;for (int i = (1 << m) - 1 - state; i; i -= lowbit(i)){int c = log2[lowbit(i)];if (t == -1 || col[t].size() > col[c].size())t = c;}// 枚举选哪行for (auto row : col[t])if (dfs(depth - 1, state | row))return true;return false;
}int main()
{cin >> n >> m >> k;for (int i = 0; i < m; i ++ ) log2[1 << i] = i;for (int i = 0; i < n; i ++ ){int state = 0;for (int j = 0; j < k; j ++ ){int c;cin >> c;state |= 1 << c - 1;}for (int j = 0; j < m; j ++ )if (state >> j & 1)col[j].push_back(state);}for (int i = 0; i < m; i ++ ){sort(col[i].begin(), col[i].end());col[i].erase(unique(col[i].begin(), col[i].end()), col[i].end());}int depth = 0;while (depth <= m && !dfs(depth, 0)) depth ++ ;if (depth > m) depth = -1;cout << depth << endl;return 0;
}

4.鸣人的影分身

dp题捏

#include 
#include using namespace std;const int N = 11;int main() {int t;  scanf("%d", &t);while (t --) {int n, m;  scanf("%d%d", &m, &n);int f[N][N] = {0}; f[0][0] = 1;for (int i = 0; i <= m; i ++) {for (int j = 1; j <= n; j ++) {f[i][j] = f[i][j - 1];if (i >= j)  f[i][j] += f[i - j][j];}}printf("%d\n", f[m][n]);}return 0;
}

5.糖果

背包问题捏

#include
using namespace std;
typedef pairPII;
typedef long long ll;
const int N=110;
int n,k;
int f[N][N];
int main()
{scanf("%d%d",&n,&k);int w;memset(f,-0x3f,sizeof f);f[0][0]=0;for(int i=1;i<=n;i++){scanf("%d",&w);for(int j=0;j