xqaz2wsx3edc @ 2023-07-19 17:27:23
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
char ss[100000],oo[100000];
int a[510000],b[510000];
void add(int *a,int *b) {
if(a[0]<b[0])a[0]=b[0];
int cr=0;
for(int i=1; i<=a[0]; i++) {
a[i]+=b[i]+cr;
cr=a[i]/10;
a[i]%=10;
}
if(cr) {
a[0]++;
a[a[0]]=cr;
}
}
void t(int *a) {
scanf("%s",ss);
a[0]=strlen(ss);
for(int i=1; i<=a[0]; i++) {
a[i]=ss[a[0]-i]-'0';
}
}
void o(int *a) {
for(int i=a[0];i>0; i--) {
cout<<a[i];
}
}
int main() {
t(a);
t(b);
add(a,b);
o(a);
}
by Perfect_Youth @ 2023-07-19 17:28:39
不需要高精度
by fanziyu @ 2023-07-19 17:44:01
不要用高精度,这只是一道简单的A+B问题
by zxx614 @ 2023-07-19 17:49:53
应该这么写
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int a[N],b[N],c[N];
void ptr(int x[],int n){
for(int i=0;i<n;i++)
cout<<x[i];
cout<<endl;
}
int main(){
string s1,s2;
cin>>s1>>s2;
reverse(s1.begin(),s1.end());
reverse(s2.begin(),s2.end());
int la,lb,lc;
la=s1.length();
lb=s2.length();
lc=max(la,lb)+1;
for(int i=0;i<la;i++)
a[i]=s1[i]-'0';
for(int i=0;i<lb;i++)
b[i]=s2[i]-'0';
// ptr(a,la);
// ptr(b,lb);
//加法模拟
for(int i=0;i<lc;i++){
c[i]+=a[i]+b[i];
c[i+1]=c[i]/10;
c[i]%=10;
}
// ptr(c,lc+1);
//倒序输出
int i=lc;
while(c[i]==0&&i>0) i--; //去除前缀0
for(;i>=0;i--)
cout<<c[i];
return 0;
}
by GoodLuckCat @ 2023-07-20 16:33:55
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <complex>
#include <cmath>
#define INF INT_MAX
using namespace std;
const int MAXN = 26; // 仅考虑小写字母
const int MAXM = 1005; // AC自动机最大模式串长度
const int MAXNODE = 1005; // AC自动机最大节点数
const int MAXP = 10005; // 可持久化AC自动机最大节点数
const int MAX_N = 1000; // 假设最大顶点数量
const int MAX_M = 1000; // 假设最大边数量
struct Node {
int next[MAXN]; // 子节点指针
int fail; // 失败指针
int id; // 当前节点的模式串编号
int cnt; // 模式串出现次数
};
Node node[MAXNODE]; // AC自动机节点
Node pNode[MAXP]; // 可持久化AC自动机节点
int root, pRoot; // AC自动机的根节点和可持久化AC自动机的根节点
int tot = 0, pTot = 0; // AC自动机节点总数和可持久化AC自动机节点总数
// 初始化AC自动机
void initACAutomaton() {
memset(node, 0, sizeof(node));
root = tot = 0;
node[root].fail = -1; // 根节点的失败指针指向-1
}
// 添加一个模式串
void addPattern(string pattern) {
int len = pattern.length();
int cur = root;
for (int i = 0; i < len; i++) {
int idx = pattern[i] - 'a'; // 将小写字母映射到0-25
if (node[cur].next[idx] == 0) { // 若当前节点不存在该子节点,则新建一个节点
node[cur].next[idx] = ++tot;
memset(&node[tot], 0, sizeof(Node));
}
cur = node[cur].next[idx]; // 移动到下一个节点
}
node[cur].id = tot; // 标记模式串编号
}
// 构建AC自动机的失败指针
void buildACAutomaton() {
queue<int> Q;
for (int i = 0; i < MAXN; i++) { // 将根节点的子节点入队
if (node[root].next[i] != 0) {
Q.push(node[root].next[i]);
}
}
while (!Q.empty()) {
int cur = Q.front();
Q.pop();
for (int i = 0; i < MAXN; i++) {
if (node[cur].next[i] != 0) {
int child = node[cur].next[i];
int fail = node[cur].fail;
while (fail != -1) { // 在失效指针链上查找
if (node[fail].next[i] != 0) { // 子节点存在,则更新失败指针
node[child].fail = node[fail].next[i];
break;
}
fail = node[fail].fail;
}
if (fail == -1) { // 无法找到匹配的子节点,则将失败指针指向根节点
node[child].fail = root;
}
Q.push(child); // 将该节点的子节点入队
}
}
}
}
// 在AC自动机上匹配文本串
void matchText(string text) {
int len = text.length();
int cur = root;
for (int i = 0; i < len; i++) {
int idx = text[i] - 'a'; // 将小写字母映射到0-25
while (node[cur].next[idx] == 0 && cur != root) { // 无法向下转移到下一个节点,则失败指针跳跃
cur = node[cur].fail;
}
cur = node[cur].next[idx]; // 向下转移到下一个节点
if (cur == 0) { // 当前字符无法匹配任何模式串,继续向下处理
cur = root;
}
int temp = cur; // 从当前节点开始,由于失效指针可能指向多个模式串节点,需要遍历所有可能的情况
while (temp != root) {
if (node[temp].id != 0) { // 若该节点是模式串节点,则模式串出现一次
node[temp].cnt++;
}
temp = node[temp].fail; // 失败指针指向下一个可能的模式串节点
}
}
}
// 初始化可持久化AC自动机
void initPersistentAutomaton() {
memset(pNode, 0, sizeof(pNode));
pRoot = pTot = 0;
pNode[pRoot].fail = -1; // 根节点的失败指针指向-1
}
// 添加一个模式串到可持久化AC自动机
int addPatternToPersistentAutomaton(int src, string pattern) {
int len = pattern.length();
int cur = src;
for (int i = 0; i < len; i++) {
int idx = pattern[i] - 'a'; // 将小写字母映射到0-25
if (pNode[cur].next[idx] == 0) { // 若当前节点不存在该子节点,则新建一个节点
pNode[cur].next[idx] = ++pTot;
memset(&pNode[pTot], 0, sizeof(Node));
}
cur = pNode[cur].next[idx]; // 移动到下一个节点
}
pNode[cur].id = pTot; // 标记模式串编号
return cur;
}
// 在可持久化AC自动机上匹配文本串
void matchTextOnPersistentAutomaton(int src, string text) {
int len = text.length();
int cur = src;
for (int i = 0; i < len; i++) {
int idx = text[i] - 'a'; // 将小写字母映射到0-25
while (pNode[cur].next[idx] == 0 && cur != pRoot) { // 无法向下转移到下一个节点,则失败指针跳跃
cur = pNode[cur].fail;
}
cur = pNode[cur].next[idx]; // 向下转移到下一个节点
if (cur == 0) { // 当前字符无法匹配任何模式串,继续向下处理
cur = pRoot;
}
int temp = cur; // 从当前节点开始,由于失效指针可能指向多个模式串节点,需要遍历所有可能的情况
while (temp != pRoot) {
if (pNode[temp].id != 0) { // 若该节点是模式串节点,则模式串出现一次
pNode[temp].cnt++;
}
temp = pNode[temp].fail; // 失败指针指向下一个可能的模式串节点
}
}
}
struct Edge {
int from, to, capacity, cost;
Edge(int from, int to, int capacity, int cost)
: from(from), to(to), capacity(capacity), cost(cost) {}
};
class MinCostMaxFlow {
private:
int n;
int source, sink;
vector<vector<int> > graph;
vector<Edge> edges;
vector<int> dist;
vector<int> parent;
vector<int> inQueue;
void addEdge(int from, int to, int capacity, int cost) {
graph[from].push_back(edges.size());
edges.push_back(Edge(from, to, capacity, cost));
graph[to].push_back(edges.size());
edges.push_back(Edge(to, from, 0, -cost));
}
// Bellman-Ford算法寻找最短路径
bool bellmanFord() {
// 初始化
fill(dist.begin(), dist.end(), INF);
fill(parent.begin(), parent.end(), -1);
fill(inQueue.begin(), inQueue.end(), 0);
dist[source] = 0;
inQueue[source] = 1;
// 队列用于广度优先搜索
queue<int> q;
q.push(source);
while (!q.empty()) {
int u = q.front();
q.pop();
inQueue[u] = 0;
for (size_t i = 0; i < graph[u].size(); i++) {
int e = graph[u][i];
int v = edges[e].to;
int w = edges[e].cost;
if (edges[e].capacity > 0 && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
parent[v] = e;
if (!inQueue[v]) {
q.push(v);
inQueue[v] = 1;
}
}
}
}
// 如果汇点未被访问,说明不存在增广路径了
return (parent[sink] != -1);
}
public:
MinCostMaxFlow(int n, int source, int sink)
: n(n), source(source), sink(sink), graph(n), dist(n), parent(n), inQueue(n) {}
// 添加一条有向边
void addDirectedEdge(int from, int to, int capacity, int cost) {
addEdge(from, to, capacity, cost);
}
// 添加一条无向边
void addUndirectedEdge(int from, int to, int capacity, int cost) {
addEdge(from, to, capacity, cost);
addEdge(to, from, capacity, cost);
}
// 最小费用最大流算法
pair<int, int> run() {
int maxFlow = 0;
int minCost = 0;
// 存在增广路径时不断进行增广
while (bellmanFord()) {
// 找到增广路径中的最小容量
int flow = INF;
for (int v = sink; v != source; v = edges[parent[v]].from) {
flow = min(flow, edges[parent[v]].capacity);
}
// 根据最小容量进行增广
for (int v = sink; v != source; v = edges[parent[v]].from) {
int e = parent[v];
edges[e].capacity -= flow;
edges[e^1].capacity += flow;
minCost += flow * edges[e].cost;
}
// 增加最大流量
maxFlow += flow;
}
return make_pair(maxFlow, minCost);
}
};
struct MyEdge {
int u, v;
int id;
};
struct Query {
int l, r;
int id;
};
int n, m; // 顶点和边的数量
int q; // 查询数量
int ans[MAX_M]; // 存储查询的答案
int cnt[MAX_N][MAX_N]; // 记录图中边的数量
int mobius[MAX_N][MAX_N]; // 存储莫比乌斯函数的值
int colors[MAX_N][MAX_N]; // 存储顶点的颜色
vector<MyEdge> edges; // 存储边的信息
vector<Query> queries; // 存储查询的信息
vector<int> adj[MAX_N]; // 存储邻接表
// 初始化
void initialize() {
for (int i = 0; i < MAX_N; i++) {
adj[i].clear();
for (int j = 0; j < MAX_N; j++) {
cnt[i][j] = 0;
mobius[i][j] = 0;
colors[i][j] = 0;
}
}
edges.clear();
queries.clear();
}
// 求解莫比乌斯函数的值
void calculateMobius() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i % j == 0) {
mobius[i][j] = 0;
} else {
mobius[i][j] = -mobius[j][i % j];
}
}
}
}
// 处理预处理混合图
void processGraph() {
for (int i = 1; i <= m; i++) {
int u = edges[i].u;
int v = edges[i].v;
int id = edges[i].id;
cnt[u][v]++; // 边权累加
colors[u][id]++; // 节点颜色计数
colors[v][id]++; // 节点颜色计数
}
}
// 对颜色计数进行修正
void adjustColors(int u, int v) {
for (int i = 0; i < adj[u].size(); i++) {
int id = adj[u][i];
int w = edges[id].u ^ edges[id].v ^ u;
cnt[v][w]--;
if (cnt[v][w] == 0) {
colors[w][id]--;
if (colors[w][id] == 0) {
ans[id] -= mobius[n][colors[w][id]];
} else {
ans[id] += mobius[n][colors[w][id]];
}
}
}
}
// 处理每个查询
void processQueries() {
for (int i = 0; i < queries.size(); i++) {
int l = queries[i].l;
int r = queries[i].r;
int id = queries[i].id;
while (r < m) {
r++;
adjustColors(edges[r].u, edges[r].v);
}
while (l > 0) {
l--;
adjustColors(edges[l].u, edges[l].v);
}
ans[id] += mobius[n][colors[edges[l].u][id]] + mobius[n][colors[edges[l].v][id]];
}
}
class UnionFind {
private:
std::vector<int> parent;
std::vector<int> rank;
public:
UnionFind(int n) {
parent.resize(n);
rank.resize(n);
for (int i = 0; i < n; ++i) {
parent[i] = i;
rank[i] = 0;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
};
// 更新树状数组中指定位置的值
void update(vector<int>& fenwickTree, int index, int value) {
int n = fenwickTree.size();
while (index < n) {
fenwickTree[index] += value;
index += index & (-index);
}
}
// 计算树状数组中前index个元素的和
int query(vector<int>& fenwickTree, int index) {
int sum = 0;
while (index > 0) {
sum += fenwickTree[index];
index -= index & (-index);
}
return sum;
}
// 结点结构体
struct TreeNode {
int sum;
TreeNode* left;
TreeNode* right;
};
// 创建新结点
TreeNode* createNode() {
TreeNode* newNode = new TreeNode;
newNode->sum = 0;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 更新结点
void update(TreeNode* root, int left, int right, int index, int value) {
if (left == right) {
root->sum += value;
return;
}
int mid = (left + right) / 2;
if (index <= mid) {
if (root->left == NULL) {
root->left = createNode();
}
update(root->left, left, mid, index, value);
} else {
if (root->right == NULL) {
root->right = createNode();
}
update(root->right, mid + 1, right, index, value);
}
root->sum = root->left->sum + root->right->sum;
}
// 查询区间和
int query(TreeNode* root, int left, int right, int queryLeft, int queryRight) {
if (root == NULL || queryLeft > right || queryRight < left) {
return 0;
}
if (queryLeft <= left && queryRight >= right) {
return root->sum;
}
int mid = (left + right) / 2;
return query(root->left, left, mid, queryLeft, queryRight) +
query(root->right, mid + 1, right, queryLeft, queryRight);
}
int fibonacci(int n) {
if (n <= 0) {
return 0;
}
if (n == 1 || n == 2) {
return 1;
}
int* dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 1;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
int result = dp[n];
delete[] dp;
return result;
}
// 定义函数指针类型
typedef void (*FunctionPtr)(int);
// 示例函数1
void function1(int num) {
std::cout << "Function 1: " << num << std::endl;
}
// 示例函数2
void function2(int num) {
std::cout << "Function 2: " << num << std::endl;
}
#define PI acos(-1)
// FFT算法
void FFT(std::complex<double> *X, int N, bool inverse) {
if (N <= 1) return;
std::complex<double> *X0 = new std::complex<double>[N / 2];
std::complex<double> *X1 = new std::complex<double>[N / 2];
for (int i = 0; 2 * i < N; ++i) {
X0[i] = X[2 * i];
X1[i] = X[2 * i + 1];
}
FFT(X0, N / 2, inverse);
FFT(X1, N / 2, inverse);
double angle = 2 * PI / N;
if (inverse) angle = -angle;
std::complex<double> w(1), wn(cos(angle), sin(angle));
for (int i = 0; 2 * i < N; ++i) {
X[i] = X0[i] + w * X1[i];
X[i + N / 2] = X0[i] - w * X1[i];
if (inverse) {
X[i] /= 2;
X[i + N / 2] /= 2;
}
w *= wn;
}
delete[] X0;
delete[] X1;
}
// 多项式逆
void PolynomialInverse(const std::complex<double> *input, std::complex<double> *B, int N) {
for (int i = 0; i < N; ++i) {
B[i] = input[i] - input[i] * input[i] * input[i];
}
}
// 元对数函数
std::complex<double> *ElementaryLogarithm(const std::complex<double> *input, int N) {
std::complex<double> *output = new std::complex<double>[N];
for (int i = 0; i < N; ++i) {
output[i] = std::log(input[i]);
}
return output;
}
int calculateFibonacci(int num_value) {
if (num_value <= 1) {
return num_value;
}
int* dp = new int[num_value + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= num_value; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
int result = dp[num_value];
delete[] dp;
return result;
}
// 分治算法: 查找数组中的最大元素
int findMaximum(const std::vector<int>& arr, int left, int right) {
// 基线情况:只剩下一个元素
if (left == right)
return arr[left];
// 分解问题:将数组分为两个子数组
int mid = (left + right) / 2;
// 解决子问题:递归地找到左子数组和右子数组的最大元素
int maxLeft = findMaximum(arr, left, mid);
int maxRight = findMaximum(arr, mid + 1, right);
// 合并解:返回左右子数组中的较大值
return (maxLeft > maxRight) ? maxLeft : maxRight;
}
int mian() {
// 初始化AC自动机
initACAutomaton();
// 添加模式串
addPattern("he");
addPattern("she");
addPattern("his");
addPattern("hers");
// 构建AC自动机的失败指针
buildACAutomaton();
// 匹配文本串
string text = "ushers";
matchText(text);
// 输出模式串出现次数
for (int i = 1; i <= tot; i++) {
if (node[i].cnt > 0) {
cout << "Pattern " << i << " appears " << node[i].cnt << " times." << endl;
}
}
// 初始化可持久化AC自动机
initPersistentAutomaton();
// 添加模式串到可持久化AC自动机
int src = addPatternToPersistentAutomaton(pRoot, "he");
addPatternToPersistentAutomaton(src, "she");
addPatternToPersistentAutomaton(src, "his");
addPatternToPersistentAutomaton(src, "hers");
// 匹配文本串
string persistentText = "ushers";
matchTextOnPersistentAutomaton(src, persistentText);
// 输出模式串出现次数
for (int i = 1; i <= pTot; i++) {
if (pNode[i].cnt > 0) {
cout << "Pattern " << i << " appears " << pNode[i].cnt << " times." << endl;
}
}
// 示例用法
int n = 4; // 点数量
int source = 0; // 源点
int sink = n-1; // 汇点
MinCostMaxFlow mcmf(n, source, sink);
// 添加有向边
mcmf.addDirectedEdge(0, 1, 2, 1);
mcmf.addDirectedEdge(1, 2, 1, 2);
mcmf.addDirectedEdge(2, 3, 1, 1);
// 添加无向边
mcmf.addUndirectedEdge(0, 2, 2, 2);
// 运行最小费用最大流算法
pair<int, int> result = mcmf.run();
// 输出结果
cout << "最大流量: " << result.first << endl;
cout << "最小费用: " << result.second << endl;
// 输入n, m, q, 顶点和边的数量以及查询数量
cin >> n >> m >> q;
// 输入边的信息
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
edges.push_back({u, v, i});
adj[u].push_back(i);
adj[v].push_back(i);
}
// 输入查询的信息
for (int i = 0; i < q; i++) {
int l, r;
cin >> l >> r;
queries.push_back({l, r, i});
}
// 初始化
initialize();
// 求解莫比乌斯函数的值
calculateMobius();
// 处理预处理混合图
processGraph();
// 处理每个查询
processQueries();
// 输出结果
for (int i = 0; i < q; i++) {
cout << ans[i] << endl;
}
// 示例使用
vector<int> fenwickTree(10, 0); // 假设树状数组的大小为10
// 更新某个位置的值
update(fenwickTree, 2, 5); // 将第2个位置的值更新为5
update(fenwickTree, 4, -2); // 将第4个位置的值减去2
// 查询前缀和
int prefixSum = query(fenwickTree, 6); // 查询前缀和前6个元素的和
cout << "Prefix sum: " << prefixSum << endl; // 输出结果
int size;
std::cout << "请输入数组的大小: ";
std::cin >> size;
TreeNode* root = createNode();
// 逐个插入元素并更新主席树
for (int i = 0; i < size; i++) {
int value;
std::cout << "请输入第 " << (i + 1) << " 个元素的值: ";
std::cin >> value;
update(root, 1, size, i + 1, value);
}
// 查询区间和
int queryLeft, queryRight;
std::cout << "请输入查询的左端点和右端点: ";
std::cin >> queryLeft >> queryRight;
int sum = query(root, 1, size, queryLeft, queryRight);
std::cout << "查询结果为: " << sum << std::endl;
int num = 10;
int fib = fibonacci(num);
std::cout << "The " << num << "th Fibonacci number is: " << fib << std::endl;
// 声明函数指针
FunctionPtr ptr;
// 赋值函数指针
ptr = &function1;
// 调用函数指针
ptr(10);
// 更新函数指针
ptr = &function2;
// 调用函数指针
ptr(20);
// 示例调用
int N = 8;
std::complex<double> *input = new std::complex<double>[N];
std::complex<double> *output = new std::complex<double>[N];
// 填充输入数组
for (int i = 0; i < N; ++i) {
input[i] = std::complex<double>(i, 0);
}
// 多项式逆
PolynomialInverse(input, output, N);
// 输出结果
for (int i = 0; i < N; ++i) {
std::cout << output[i].real() << " ";
}
std::cout << std::endl;
// 元对数函数
ElementaryLogarithm(input, N);
// 输出结果
for (int i = 0; i < N; ++i) {
std::cout << output[i].real() << " ";
}
std::cout << std::endl;
delete[] input;
delete[] output;
double base = 2.0; // 指数函数的底数
double exponentiation = exp(base); // 计算e的x次方
std::cout << "The result of exponentiation is: " << exponentiation << std::endl;
int num_value = 10;
int fib_num = calculateFibonacci(num_value);
std::cout << "The Fibonacci number at position " << num_value << " is: " << fib_num << std::endl;
std::vector<int> arr;
arr.push_back(3);
arr.push_back(7);
arr.push_back(2);
arr.push_back(9);
arr.push_back(1);
arr.push_back(5);
arr.push_back(4);
int max = findMaximum(arr, 0, arr.size() - 1);
std::cout << "Max element: " << max << std::endl;
return 0;
}
int main()
{
int a,b;
cin>>a>>b;
cout<<a+b;
}
by Noah_Shen @ 2023-07-22 16:30:02
干嘛不直接用 cout << a + b;
by goIdie @ 2023-07-22 21:14:52
楼上的楼上的代码。。。。。
by goIdie @ 2023-07-22 21:16:12
800多行。。。
by I_AM_AC_KING @ 2023-07-23 11:31:11
不用高精度,高精度反而会错,因为数据中有负数。
by Him_jntm @ 2023-07-23 23:05:34
@Huyuhao0215有必要吗 直接
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long a,b,sum=0;
cin>>a>>b;
sum=a+b;
cout<<sum;
return 0;
}
by Lordlyt @ 2023-07-24 09:00:42
@Him_jntm 那个哥们代码的有效部分都在主函数里面,一共就三行(